归并排序实现中合并后数组未更新的问题求助

核心问题分析 #

1. combine2函数的逻辑错误 #

在combine2的else分支中，错误地将left[l]加入结果数组，而正确操作应该是添加right[r]。这会导致合并时右侧数组的元素无法被正确加入，反而重复添加左侧元素，直接破坏了合并后的有序性。

2. merge_sort的赋值与返回问题 #

merge_sort函数中，array = combine2(left, right)只是给当前函数的局部变量array重新赋值，并不会修改上层递归中对应的原列表（Python中列表是可变对象，但此处的array是切片生成的新列表的引用，赋值操作不会影响上层的列表对象）。同时，函数没有返回排序后的数组，上层调用无法获取正确的排序结果。

修正后的代码 #

修复combine2函数 #

def combine2(left, right):
    l = r = 0
    array = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            array.append(left[l])
            l += 1
        else:
            # 修复：添加right[r]而非left[l]
            array.append(right[r])
            r += 1
    # 简化剩余元素处理
    array.extend(left[l:])
    array.extend(right[r:])
    return array

修复merge_sort函数 #

改为返回排序后的数组，递归调用时接收返回的结果：

def merge_sort(array):
    if len(array) == 1:
        return array
    k = len(array) // 2
    # 递归获取排序后的左右子数组
    left = merge_sort(array[k:])
    right = merge_sort(array[:k])
    sorted_array = combine2(left, right)
    print(sorted_array)
    return sorted_array

# 调用并获取最终结果
result = merge_sort([8,7,6,5,4,3,2,1])
print("最终排序结果:", result)

修正后的输出 #

运行上述代码后，输出会变为：

[7, 8]
[5, 6]
[5, 6, 7, 8]
[1, 2]
[3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7, 8]
最终排序结果: [1, 2, 3, 4, 5, 6, 7, 8]

内容的提问来源于stack exchange，提问作者dao minh duy