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

Question

在大小不超过 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 的列表。为什么？

Answer 1

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

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

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