mergesort python实现

Question

我已经看到了很多mergesort python实现，我想到了以下代码。一般逻辑工作正常，但未返回正确的结果。非常感谢您的帮助。

代码：

def merge(left, right):
    temp = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            temp.append(left[i])
            i = i + 1
        else:
            temp.append(right[j])
            j = j+ 1
    print("i = ", i, "j = ", j)
    while i < len(left):
        temp.append(left[i])
        i += 1
    while j < len(right):
        temp.append(right[j])
        j += 1
    print("Returned from merge", temp)
    return temp

def mergesort(data):
    if len(data) < 2:
        return
    left = data[:len(data)//2]
    print(left)
    right = data[len(data)//2:]
    print(right)
    print("left only now")
    mergesort(left)
    print("right now")
    mergesort(right)
    return merge(left,right)

data = mergesort([1,20, 30, 25, 8, 7, 9])

在主mergesort函数中，我认为最后一行不正确。

Answer 1

您调用的mergesort不会修改其参数，而是返回一个新的排序列表。

一个简单的解决方法是：

def mergesort(data):
    if len(data) < 2:
        return data              # Fix1
    left = data[:len(data)//2]
    print(left)
    right = data[len(data)//2:]
    print(right)
    print("left only now")
    left = mergesort(left)       # Fix2
    print("right now")
    right = mergesort(right)     # Fix3
    return merge(left,right)

data = mergesort([1,20, 30, 25, 8, 7, 9])