归并排序统计移位次数时单个数组计算结果错误问题求助

问题原因 #

你的代码统计移位次数的核心逻辑存在计算错误：
当右半部分元素小于左半部分当前指针位置的元素时，实际需要累加的移位次数是左半部分剩余未处理的所有元素的数量，也就是左半部分总长度 - 左指针当前位置，或者等价的len(left[x:])。你在原有代码中多减了一次左指针x，导致计数结果偏小。

原错误代码行：

count += len(left[x:])-x

修复方法 #

将上述代码行修改为以下任意一种即可：

# 写法1：计算效率更高，不需要切片
count += len(left) - x

# 写法2：和你原有写法逻辑一致，去掉多余的减x操作
count += len(left[x:])

补充说明 #

你当前的归并流程没有将遍历结束后剩余的左/右半部分元素追加到结果数组中，如果你只需要统计移位次数，这部分逻辑不影响最终计数结果；如果你后续需要返回排序后的数组，需要在while循环结束后补充以下代码：

result.extend(left[x:])
result.extend(right[y:])

修改后完整可运行代码 #

def mergeSort(arr):
    count = x = y = 0
    result =[]
    arrayLength = len(arr)

    if arrayLength <= 1:
        return count
    
    middle = arrayLength // 2
    left = arr[:middle]
    right = arr[middle:]

    leftLength = len(left)
    rightLength = len(right)

    count += mergeSort(left) 
    count += mergeSort(right)
    
    while x < leftLength and y < rightLength:
        if left[x] <= right[y]:
            result.append(left[x])
            x += 1
        else:
            result.append(right[y])
            y += 1
            # 修复后的计数逻辑
            count += len(left) - x
    # 若需要返回排序后数组，取消注释下方两行
    # result.extend(left[x:])
    # result.extend(right[y:])
    return count


arr = [1,20,6,4,5]
print(mergeSort(arr))

arr2 = [4,3,2,1]
print(mergeSort(arr2))

arr3=[1, 1, 1, 2, 2]
print(mergeSort(arr3))

arr4=[2, 1, 3, 1, 2]
print(mergeSort(arr4))

arr5 = [12,15,1,5,6,14,11]
print(mergeSort(arr5))

arr6=[3, 5, 7, 11, 9]
print(mergeSort(arr6))

修改后你提到的返回值为3的测试数组[2, 1, 3, 1, 2]会正确输出4，符合预期结果。

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