Python- Mergesort递归误差

Question

我使用递归在Python中制作了一个Mergesort程序，并且我不断遇到有关第27行，第23行，第18行和递归错误的错误：
" recursionError：相比之下超过了最大递归深度"，但我似乎在代码中没有发现任何明显的错误。

def merge(list, start, middle, end):
    L = list[start:middle]
    R = list[middle:end+1]
    L.append(99999999999)
    R.append(99999999999)
    i = j = 0
    for k in range(start, end+1):
        if L[i] <= R[j]:
            list[k] = L[i]
            i += 1
        else:
            list[k] = R[j]
            j+=1
def mergesort2(list, start, end):
    if start < end:
        middle = (start + end)//2
        mergesort2(list, start, end)
        mergesort2(list, middle+1, end)
        merge(list, start, middle, end)
def mergesort(list):
    mergesort2(list, 0, len(list)-1)

mylist = [8,23,4,56,75,21,42,10,2,5]
mergesort(mylist)
print(mylist)

谢谢

Answer 1

def mergesort2(list, start, end):
    if start < end:
        middle = start + (end - start)//2
        mergesort2(list, start, middle) // notice middle instead of end.
        mergesort2(list, middle+1, end)
        merge(list, start, middle, end)

您在相同的列表中递归而没有减小其大小，因此它永远不会达到基本情况。

编辑：同样，中间应由start + (end-start)/2而不是(start+end)/2计算，以避免使用大型数组时整数溢出错误。这是一个很好的做法。

编辑2：在进一步分析代码之后，我发现输出是错误的。我试图纠正它们，这是我的代码：

def merge(start, middle, end):
    L = l[:middle]
    R = l[middle:]
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j+=1
        k += 1
    while i < len(L):
        l[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        l[k] = R[j]
        j += 1
        k += 1
def mergesort2(start, end):
    if start < end:
        middle = start + (end - start)//2
        mergesort2(start, middle)
        mergesort2(middle+1, end)
        merge(start, middle, end)
def mergesort(l):
    mergesort2(0, len(l)-1)

l = [8,23,4,56,75,21,42,10,2,5]
mergesort(l)
print(l)

要注意几点：

• 将变量名称从list更改为l，以免与关键字list混淆。

• 没有使用列表到每个函数的使用情况，因为它已经被声明为全局变量。

• merge()有一些问题。循环实际上应从0运行，直到两个列表的长度都没有交叉为止。如果越过，只需复制其余元素。

• 使用了适当的python剪接技术：p