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

Question

下面是我尝试用python实现的一个简单的合并排序算法。我试图在不使用在别处找到的left和right参数的情况下这样做，只使用切片。

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 sys.setrecursionlimit(10000)

如果算法没有结束，则重试，您将有一个无限循环