python合并排序实现错误:超过了最大递归深度

Question

下面是我尝试在python中实现的一个简单的合并排序算法。我试着在不使用其他地方找到的左右参数的情况下做到这一点，只使用切片。

from math import floor

def merge(A, B):
"""Mearges the two sorted lists A and B"""
merged = []
i, j = 0, 0
while i < len(A) and j < len(B):
if A[i] <= B[j]:
merged.append(A[i])
i += 1
else:
merged.append(B[j])
j += 1

if j == len(B):
merged.extend(A[i:])
elif i == len(A):
merged.extend(B[j:])

return merged
def merge_sort(A):
if len(A) == 1:
return A

m = floor(len(A) / 2)
half1 = A[0:m]    
half2 = A[m:]
A = merge_sort(half1)
B = merge_sort(half2)
R = merge(A, B)
return R

def main():
C = [6, 7, 2]
print(merge_sort(C))
exit()
if __name__ == "__main__":
main()

而且效果很好。但当我尝试时

A = merge_sort(A[0:m])
B = merge_sort(A[m:])

我没有在merge_sort函数中使用变量half1和half2，而是得到了：

Traceback (most recent call last):
File "/home/aayush/PyProgs/mrg_sort.py", line 44, in <module>
main()
File "/home/aayush/PyProgs/mrg_sort.py", line 40, in main
print(merge_sort(C))
File "/home/aayush/PyProgs/mrg_sort.py", line 32, in merge_sort
B = merge_sort(A[m:])
File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
A = merge_sort(A[0:m])
File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
A = merge_sort(A[0:m])
File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
A = merge_sort(A[0:m])
[Previous line repeated 993 more times]
File "/home/aayush/PyProgs/mrg_sort.py", line 25, in merge_sort
if len(A) == 1:
RecursionError: maximum recursion depth exceeded while calling a Python object

请告诉我我做错了什么。

Answer 1

您只需要检查变量命名，因为这里A是更新的，您使用的是列表数据，而不是原始的

def merge_sort(A):
if len(A) == 1:
return A

m = floor(len(A) / 2)
c = merge_sort(A[0:m])
B = merge_sort(A[m:])
R = merge(c, B)
return R

Answer 2

您尝试过使用较小的数据吗？

尝试：

导入系统sys.setrecursionlimit(10000(

然后重试如果算法没有结束，你有一个无限循环