合并排序"maximum recursion depth exceeded in comparison "

Question

我想在Python 3中编写合并排序代码。

这是我的代码：

import math
def Merge(array,start,mid,end):
n1 = mid - start +1
n2 = end - mid
i = 0
j = 0
left = [None] * n1
right = [None] * n2
inv = 0
for i in range(0,n1):
left[i] = array[start + i - 1]
for j in range(0,n2):
right[j] = array[mid + j]
left.append(math.inf)
right.append(math.inf)
new_list = []
for k in range(0,end):
if left[i] <= right[j]:
array[k] = left[i]
i+=1
elif left[i] > right[j]:
array[k] = right[j]
j+=1
def MergeSort(array,start,end):
if len(array) <= 1:
return array
mid = math.ceil((start + end)/2)
MergeSort(array,start,mid)
MergeSort(array,mid+start,end)
Merge(array,start,mid,end)

stuff = [1, -5, 17, 32, 6] 
MergeSort(stuff, 0, len(stuff))
print(stuff)

我测试了第一个函数(合并(，它正常工作。但是我对递归有问题。我不知道问题出在哪里。错误是"比较中超过了最大递归深度"。

Answer 1

您没有功能退出MergeSort。 列表的长度永远不会改变，因为您在每次调用时都会传递整个列表。 如果从列表中的 5 个元素开始，则len(array)始终为 5。 结果，你得到了左手边的基本项目(一个元素(，并继续永远敲打那个元素。

尝试检查边界，例如

if end - start <= 1:

这至少会让你进入下一个执行问题。

---

请参阅这个可爱的调试博客以获取帮助。 如果没有别的，请学习放入有用的print语句来跟踪数据和控制流。