在python中执行mergesort算法变化的索引超出范围？

Question

基于我从CLRS书中学到的东西，我已经在python中完成了我的合并排序算法的一个变体，并将它与麻省理工学院介绍性计算机科学书上的实现进行了比较。我在我的算法中找不到问题，IDLE给我一个超出范围的索引，尽管对我来说一切都很正常。我不确定这是否是由于麻省理工学院算法中的借鉴想法造成的混乱（见下文）。

lista = [1,2,3,1,1,1,1,6,7,12,2,7,7,67,4,7,9,6,6,3,1,14,4] 

def merge(A, p, q, r): 
    q = (p+r)/2 
    L = A[p:q+1] 
    R = A[q+1:r] 

    i = 0 
    j = 0 

    for k in range(len(A)): 

     #if the list R runs of of space and L[i] has nothing to compare 
     if i+1 > len(R): 
      A[k] = L[i] 
      i += 1 

     elif j+1 > len(L): 
      A[k] = R[j] 
      j += 1 

     elif L[i] <= R[j]: 
      A[k] = L[i] 
      i += 1 

     elif R[j] <= L[i]: 
      A[k] = R[j] 
      j += 1 

     #when both the sub arrays have run out and all the ifs and elifs done, 
     # the for loop has effectively ended 

    return A 


def mergesort(A, p, r): 
    """A is the list, p is the first index and r is the last index for which 
     the portion of the list is to be sorted.""" 
    q = (p+r)/2 
    if p<r: 
     mergesort(A, p, q) 
     mergesort(A, q+1, r) 
     merge (A, p, q, r) 
    return A 

print mergesort(lista, 0, len(lista)-1) 

我已经尽可能靠近我可以跟着CLRS的伪代码，只是不使用“无限值”的L和R的结束，这将继续比较（这是效率不高？）。我试图在麻省理工学院的书中加入这样的想法，即简单地将剩余的L或R列表复制到A，以便变异A并返回一个排序列表。但是，我似乎无法找到它出了什么问题。另外，我不明白为什么伪代码需要'q'作为输入，因为q对于中间索引计算为（p + q）/ 2。另一方面，从MIT的书中，我们看到了一些看起来非常优雅的东西。

def merge(left, right, compare): 
    """Assumes left and right are sorted lists and 
compare defines an ordering on the elements. 
Returns a new sorted(by compare) list containing the 
same elements as(left + right) would contain. 
""" 
    result = [] 
    i, j = 0, 0 

    while i < len(left) and j < len(right): 
     if compare(left[i], right[j]): 
      result.append(left[i]) 
      i += 1 
     else : 
      result.append(right[j]) 
      j += 1 

    while (i < len(left)): 
     result.append(left[i]) 
     i += 1 

    while (j < len(right)): 
     result.append(right[j]) 
     j += 1 

    return result 

import operator 

def mergeSort(L, compare = operator.lt): 
    """Assumes L is a list, compare defines an ordering 
on elements of L. 
Returns a new sorted list containing the same elements as L""" 
if len(L) < 2: 
    return L[: ] 
else : 
    middle = len(L) //2 
left = mergeSort(L[: middle], compare) 
right = mergeSort(L[middle: ], compare) 
return merge(left, right, compare) 

哪里可能出错了？

另外，我认为麻省理工学院实施的关键区别在于它创建了一个新的列表，而不是改变原始列表。这使我很难理解mergesort，因为我发现CLRS的解释非常清楚，通过理解它可以根据不同层次的递归排序原始列表中最细小的组件（长度为1的列表排序），从而在旧列表本身中“存储”递归结果。

但是，再次思考，是否正确地说，MIT算法中的每个递归所返回的“结果”反过来又结合在一起？

谢谢！

Answer 1

您的代码和MIT之间的根本区别是mergesort函数中的条件语句。当你的if语句是：

if p<r: 

他们是：

if len(L) < 2: 

这意味着，如果你有，在递归调用树中的任意点，列表是len(A) == 1，那么它仍然会在尺寸1或甚至0列表上调用merge。您可以看到这会导致合并函数中出现问题，因为那么您的L,R或两个子列表最终可能会为0，如果出现界限索引错误，则会导致出错。

您的问题然后可以通过改变很容易解决您的if语句的东西都到他们的，像len(A) < 2或r-p < 2