Python归并排序（Mergesort）输出异常问题排查求助

你的归并排序逻辑本身是正确的，但输入使用了numpy数组而非普通Python列表，这是导致结果异常的核心原因：

• numpy数组的切片（myList[:mid]）是原数组的视图，而非独立副本。递归调用mergeSort(left)时，对left的修改会直接影响原myList的对应区域，导致合并阶段使用的是被污染的数组片段，最终出现重复元素、排序错误等问题。
• 普通Python列表的切片是独立副本，递归排序后的left/right是干净的排序结果，合并逻辑可以正常工作。

修复步骤 #

1. 将numpy数组转为普通列表：
   修改代码中myList = list1为myList = list(list1)，确保输入是普通Python列表。

2. 验证示例输入：
   用你提供的测试列表[267,168,236,190,2,500,4,45,86]测试，修复后的代码会输出正确的排序结果：[2, 4, 45, 86, 168, 190, 236, 267, 500]。

修复后的完整代码 #

import numpy as np

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        mergeSort(left)
        mergeSort(right)

        i = j = k = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                myList[k] = left[i]
                i += 1
            else:
                myList[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k] = right[j]
            j += 1
            k += 1

# 生成随机numpy数组并转为普通列表
list1 = np.random.randint(low=1, high=800, size=100)
myList = list(list1)

print("Given array is")
print(myList)

mergeSort(myList)

print("\nSorted array is:")
print(myList)

额外说明 #

如果需要直接对numpy数组进行排序，推荐使用numpy内置的np.sort()方法，它经过优化，性能远高于手动实现的归并排序。如果坚持手动实现，需要针对numpy数组的视图特性调整逻辑，比如每次递归时创建切片的副本（left = myList[:mid].copy()），但这会增加额外的内存开销。

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