You need to enable JavaScript to run this app. 我编写的Python归并排序实现是否正确,为何测试速度偏快?
优惠活动
大模型
产品
解决方案
定价
更多

我编写的Python归并排序实现是否正确,为何测试速度偏快?

结论

这段归并排序的核心功能逻辑没有错误,能够正确输出升序排序结果,10个元素下测试比冒泡排序快4倍属于正常表现,不是实现出了问题,但代码确实存在几个会严重影响大数据量下性能的疏漏。

功能正确性验证

从逻辑上看,两个函数的流程符合归并排序的标准要求:

  • merge函数通过双向比较取更小值加入结果集,最后拼接两个输入列表的剩余部分,没有逻辑偏差
  • merge_sort的递归对半切分、自底向上归并的流程也没有错误
    可以通过简单用例验证:
# 测试merge函数逻辑
merge([2,5,7], [1,3,6]) # 返回 [1,2,3,5,6,7] 符合预期
# 测试归并排序逻辑
merge_sort([3,1,4,1,5,9,2,6]) # 返回 [1,1,2,3,4,5,6,9] 符合预期

小数据量下的性能表现是正常的

觉得“10个元素快4倍不合理”,本质是对算法复杂度和Python层常数开销的认知偏差:

  • 无优化的冒泡排序时间复杂度是O(n²),10个元素的场景下最多要完成近100次比较、交换操作,所有操作都是纯Python层的循环执行
  • 哪怕当前实现有不小的性能缺陷,10个元素的场景下,归并的总循环次数远少于冒泡的双循环,即便有额外操作开销,测出来快3-5倍是非常正常的,和算法本身的设计不冲突。

代码实际存在的问题(不影响结果正确性,但会大幅降低性能)

1. merge函数的pop(0)性能陷阱

Python列表基于动态数组实现,pop(0)的时间复杂度是O(k)(k为当前列表长度)——删除首元素后,需要把后续所有元素整体向前移动一位才能维持数组结构。
这个操作会把原本O(n)的merge过程拉成O(n²)复杂度,直接抵消归并排序分治的复杂度优势。比如处理1000个以上元素的列表时,这个实现的性能会暴跌,甚至比写的很差的冒泡排序还慢。
修正这部分的标准写法是改用双下标指针遍历,不修改原输入列表:

def merge(arr1, arr2):
    returned = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] >= arr2[j]:
            returned.append(arr2[j])
            j += 1
        else:
            returned.append(arr1[i])
            i += 1
    returned.extend(arr1[i:])
    returned.extend(arr2[j:])
    return returned

2. 空列表边界的疏漏

当前merge_sort的递归终止条件只处理了长度为1的列表,如果传入空列表,既不满足终止条件,也无法正常触发递归流程,最终会返回None。这属于边界bug,只是测试10个元素的场景没有触发而已。
修正后的递归逻辑:

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    middle = len(nums) // 2
    return merge(merge_sort(nums[:middle]), merge_sort(nums[middle:]))

3. 不必要的列表拷贝

原merge函数中用returned = returned + arr1拼接剩余列表,每次拼接都会生成全新的列表对象,带来不必要的内存开销,改用extend方法原地追加可以减少这类损耗。

内容的提问来源于stack exchange,提问作者dgoodie

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 08:45:10