达到最大递归深度归并排序

Question

我一直在尝试实现合并排序，但我一直运行进入 "Maximum Recursion Depth" 错误。我目前的理论是 "if listlen <= 1:" 没有捕捉到它，但我不明白为什么

def mergesort(listin):
    listlen = len(listin)

    if listlen <= 1:
        return listin

    left = []
    right = []
    i = 0
    while i < listlen:
        if i <= listlen / 2:
            left.append(listin[i])
        else:
            right.append(listin[i])
        i += 1

    left = mergesort(left)
    right = mergesort(right)


    return merge(left, right)

def merge(listlef, listrig):
    result = []

    while len(listlef) != 0 and len(listrig) != 0:
        if listlef[0] <= listrig[0]:
            result.append(listlef[0])
            listlef = listlef[1:]
        else:
            result.append(listrig[0])
            listrig = listrig[1:]

    while len(listlef) != 0:
        result.append(listlef[0])
        listlef = listlef[1:]
    while len(listrig) != 0:
        result.append(listrig[0])
        listrig = listrig[1:]

    return result

Answer 1

对于大小为 2 的列表，请注意 i 只会是 0 和 1，两者都小于或等于 2/1 == 1。

不过，与其摆弄索引，不如交替使用您附加到的列表：

left = []
right = []
for item in listin:
    left.append(item)
    left, right = right, left

达到最大递归深度归并排序

Maximum Recursion Depth reached Merge Sort

python

recursion

mergesort

达到最大递归深度 归并排序

Maximum Recursion Depth reached Merge Sort

python

recursion

mergesort

达到最大递归深度归并排序