如何排查归并排序实现中merge函数的错误？

我一眼就揪出你merge函数里的关键问题了——sIndex的初始值设置完全错了！

错误定位 #

你的merge函数里，这行代码是导致所有问题的根源：

sIndex = lIndex  # lIndex初始为0，所以sIndex从数组第0位开始

但我们要合并的是原数组中left到right的目标区间，不是从数组的起始位置（0）开始覆盖！这直接造成了两个诡异现象：

• 数组左侧被错误覆盖成了部分排序的内容（因为每次merge都从0位开始写）
• 右侧本该被合并的区间完全没被改动（你根本没写到那些位置）

修复方案 #

把sIndex的初始值改成left就搞定了：

# 替换原来的sIndex = lIndex
sIndex = left

修复后的完整merge函数 #

修改后的代码如下：

def merge(toSort, left, right, mid):
    leftList = toSort[left:mid+1]
    rightList = toSort[mid+1:right+1]
    lIndex = 0
    rIndex = 0
    sIndex = left  # 这里是修复的核心！
    while lIndex < len(leftList) and rIndex < len(rightList):
        if leftList[lIndex] <= rightList[rIndex]:
            toSort[sIndex] = leftList[lIndex]
            lIndex += 1
        else:
            toSort[sIndex] = rightList[rIndex]
            rIndex += 1
        sIndex += 1
    while lIndex < len(leftList):
        toSort[sIndex] = leftList[lIndex]
        lIndex += 1
        sIndex += 1
    while rIndex < len(rightList):
        toSort[sIndex] = rightList[rIndex]
        rIndex += 1
        sIndex += 1

后续排查思路总结 #

你之前怀疑rightList的问题是方向偏了，下次遇到这类排序bug可以这么查：

• 在merge函数开头打印当前处理的left、mid、right区间，以及leftList、rightList，确认子数组拆分是正确的
• 打印每次赋值时的sIndex和对应的toSort位置，能快速发现你是不是在错误的位置修改原数组
• 对比正确实现时，重点关注子数组索引和原数组索引的映射关系——子数组的0位对应原数组的left位，不是原数组的0位

内容的提问来源于stack exchange，提问作者Shnuce