python之我的合并排序实现有什么问题

在大小不超过 N = ~1950 左右的较小列表中，我得到了正确的输出...但是，列表大小不会大很多会返回错误，而不是预期的结果。我的代码:

def merge(left, right, aux=[]): 
    if left == []: 
        for x in right: 
            aux.append(x) 
        return aux 
    elif right == []: 
        for x in left: 
            aux.append(x) 
        return aux 
    elif left[0] > right[0]: 
        aux.append(right[0]) 
        return merge(left, right[1:], aux) 
    else: 
        aux.append(left[0]) 
        return merge(left[1:], right, aux) 
 
def msort(values): 
    size = len(values) 
 
    if size == 1: 
        return values 
    else: 
        mid = size/2 
        return merge(msort(values[:mid]), msort(values[mid:]), []) 

在这些测试列表上运行 msort 会得到预期的(升序)输出:

val = [x for x in range(1950, 0, -1) 
val = [x for x in range(4,0,-1)] 

例如[1,2,3,...,1948,1949,1950] 和 [1,2,3,4]

但是，当我在此测试用例上运行 msort 时:

val = [x for x in range(2000,0,-1)] 

我现在收到此错误(在多次回溯到 merge 之后):

RuntimeError: maximum recursion depth exceeded in cmp 

所以我的问题是:我在这里的实现出了什么问题？我不能将它用于 N ~ >=2000 的列表。为什么？

请您参考如下方法:

问题是您正在递归地进行合并。正如所指出的，可以调用 merge(msort(left),msort(right))，但是由于您的 merge 函数实际上调用自身来进行合并，所以您重新达到递归限制。

考虑对长度为 1000 的列表调用 merge 函数。

要合并这些列表，您需要进行 2000 次合并调用(因为每次调用只将 ~1 个元素添加到 aux)。