python - 为什么这个 python 实现的归并排序不起作用？

Question

当我输入 [8,7,6,5,4,3,2,1] 时，输出为 => [4, 3, 2, 1, 8, 7 , 6, 5].

似乎与工作解决方案(比较 here )唯一不同的是，我有一个 k 变量，而不是 sorted 列表递增，并更新 arr[k] 代替 sorted。

为什么这不起作用？更新 arr[k] 是如何工作的？看来您会通过更新原始输入数组来丢失数据。

def mergesort(arr):
    if len(arr) == 1:
        return

    else:
        mid = len(arr)/2
        left = arr[0:mid]
        right = arr[mid:len(arr)]

        sorted = []
        i = 0
        j = 0
        mergesort(left)
        mergesort(right)

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted.append(left[i])
                i += 1
            else:
                sorted.append(right[j])
                j += 1

        while i < len(left):
            sorted.append(left[i])
            i += 1

        while j < len(right):
            sorted.append(right[j])
            j += 1

        return sorted

Answer 1

您应该只分配给 left 和 right 变量，因为您的函数在排序后返回排序列表，同样在基本情况下，您应该返回一个列表并使用 // 进行整数除法检查此代码

def mergesort(arr):
    if len(arr) == 1:
        return arr

    else:
        mid = len(arr)//2
        left = arr[0:mid]
        right = arr[mid:len(arr)]

        sorted = []
        i = 0
        j = 0
        left = mergesort(left) #left is now sorted
        right = mergesort(right)

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted.append(left[i])
                i += 1
            else:
                sorted.append(right[j])
                j += 1

        while i < len(left):
            sorted.append(left[i])
            i += 1

        while j < len(right):
            sorted.append(right[j])
            j += 1

        return sorted

print (mergesort([8,7,6,5,4,3,2,1,3]))