为什么我在 Python 中实现的合并排序不起作用

Question

这是我在 Python 中实现的合并排序，它不起作用：

def merge_sort(data: list) -> list:
    if len(data) > 1:
        mid = len(data) // 2
        L = data[:mid]
        R = data[mid:]

        merge_sort(L)
        merge_sort(R)

        # merge two halves
        data = merge(L, R)

def merge(L, R):
    i = j = k = 0
    temp = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            temp.append(L[i])
            i += 1
        else:
            temp.append(R[j])
            j += 1
        k += 1
    temp[k:] = L[i:] + R[j:]
    return temp

但是，稍作改动便可正常工作

def merge_sort(data: list) -> list:
    if len(data) > 1:
        mid = len(data) // 2
        L = data[:mid]
        R = data[mid:]

        merge_sort(L)
        merge_sort(R)

        # changes here
        merge(data, L, R)

def merge(data: list, L, R):
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1
        k += 1
    data[k:] = L[i:] + R[j:]

我觉得这两个实现基本相同，如果有人能指出第一个实现有什么问题以及它与第二个实现有何不同，我将不胜感激。

Answer 1

您的 merge_sort 函数忽略 merge 的 return 值；如所写，它需要一个 merge 函数来对其参数 in-place 进行排序，而不是 return 创建一个新列表。

请注意，因为工作 merge 将整个列表作为参数，所以您不需要构造子列表来合并；传递定义子列表的下索引和上索引就足够了。然后，您将使用 L 和 R 代替 len(L) 和 len(R)（对 i、j 的起始值进行适当调整，和 k).

为什么我在 Python 中实现的合并排序不起作用

Why does my implementation of merge sort in Python not work

python

mergesort