在python中实现归并排序算法的一个变体时，索引超出范围

Question

基于我从CLRS书中学到的知识，我用python完成了我的归并排序算法的一个变体，并将其与MIT的介绍性计算机科学书籍中的实现进行了比较。我无法在我的算法中找到问题，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。为什么需要把p

另一方面，从麻省理工学院的书中，我们有一些看起来非常优雅的东西。

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)

我哪里出错了?

另外，我认为MIT实现的关键区别在于它创建了一个新列表，而不是改变原始列表。这使得我很难理解归并排序，因为我发现CLRS的解释非常清楚，通过将其理解为对原始列表(长度为1的列表不需要排序)的最小组件进行排序的不同递归层，从而将递归结果"存储"在旧列表本身中。

然而，再思考一下，是否可以说MIT算法中每个递归返回的"结果"依次组合?

谢谢!

Answer 1

您的代码与MIT之间的根本区别在于合并排序函数中的条件语句。其中if语句为:

if p<r:

他们的是:

if len(L) < 2:

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

你的问题可以很容易地通过改变你的if语句类似于他们的东西，如len(A) < 2或r-p < 2