python - python中的合并排序实现给出不正确的结果

Question

我正在尝试实现 Jeff Erickson 在第 3 页上的这些注释中描述的合并排序算法。但即使该算法是正确的并且我的实现似乎是正确的，我还是将输入列表作为输出而不做任何更改。有人可以指出其中的异常情况（如果有的话）。

def merge(appnd_lst, m):
    result = []
    n = len(appnd_lst)
    i, j = 0, m
    for k in range(0, n):
        if j < n:
            result.append(appnd_lst[i])
            i += 1
        elif i > m:
            result.append(appnd_lst[j])
            j += 1
        elif appnd_lst[i] < appnd_lst[j]:
            result.append(appnd_lst[i])
            i += 1
        else:
            result.append(appnd_lst[j])
            j += 1

    return result


def mergesort(lst):
    n = len(lst)
    if n > 1:
        m = int(n / 2)
        left = mergesort(lst[:m])
        right = mergesort(lst[m:])

        appnd_lst = left
        appnd_lst.extend(right)
        return merge(appnd_lst, m)
    else:
        return lst


if __name__ == "__main__":
    print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])

Answer 1

您的合并函数中有三个错误，几个索引错误并使用了错误的比较运算符。记住 python 列表索引从 0 .. len(list)-1 开始。

* ...
6        if j > n-1:  # operator wrong and off by 1
* ...
9        elif i > m-1: # off by 1
* ...