如何修复合并排序，因为它会将我的数组还原为未排序的数组？

Question

我正在尝试在python中创建递归合并排序功能，但是我的代码无法正常工作。它首先将代码分成1个单元格数组，然后合并并将它们排序在一起。但是，在合并的第二层，函数将还原为尚未排序的数组。我想知道如何使我的代码适合我的排序工作。

def merge(list1, list2):
    count1 = count2 = 0
    final = []
    while count1 < len(list1) and count2 < len(list1):
        if list1[count1] <= list2[count2]:
            final.append(list1[count1])
            count1 += 1
        else:
            final.append(list2[count2])
            count2 += 1
    if count1 == len(list1):
        for i in range(count2, len(list2)):
            final.append(list2[i])
    else:
        for i in range(count1, len(list1)):
            final.append(list1[i])
    return final


def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        merge_sort(list1)
        merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        print(merge(list1,list2),"merge")
        return merge(list1, list2)


numbers = [2, 1, 3, 4, 6, 5, 8, 7]
print(merge_sort(numbers))

当我输入时[2, 1, 3, 4, 6, 5, 8, 7]，它被分成多个单元格。然后合并和排序，[1,2]，[3,4]，[5,6]，[7,8]。但是，下一次合并将还原排序。[2,1] + [3,4] = [2,1,3,4]，[6,5] + [8,7] = [6,5,8,7]。[2, 1, 3, 4, 6, 5, 8, 7]最后返回。

Answer 1

总体来说结构是对的。但这段代码中只有三个较小的错误。

第一个只是 list1 而不是 list2 的拼写错误。在合并函数中，while循环应该有条件while count1 < len(list1) and count2 < len(list2):

接下来是 merge_sort 函数。递归调用merge_sort时需要更新list1和list2。目前 list1 和 list2 始终保持未排序状态，这就是值不移动的原因。（见下文更新）

最后，您忘记了 len(nums)==1 时的基本情况。在这种情况下，列表已经排序，因为只有一个值。您仍然需要返回该列表，但否则不会返回 None 。

合并排序应更新为：

def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        #need to update list1 and list2
        list1 = merge_sort(list1)
        list2 = merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        new_list = merge(list1,list2)
        print(new_list,"merge")
        return new_list
    #need a base condition
    else:
        return nums