我编写的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
相关产品推荐
相关产品推荐

