为何自研归并排序代码远慢于Python内置sort()方法？

这是刚接触排序算法的同学常会遇到的问题，我来帮你拆解背后的原因，以及可以优化的方向：

核心性能差距的原因 #

1. 内置排序的底层优势
   Python默认的sort()和sorted()用的是Timsort算法——这是一种融合了归并排序与插入排序的混合优化算法，而且核心逻辑完全用C语言实现。C的执行效率比纯Python代码高几个数量级，这是两者性能差距最主要的来源。

2. 你的实现存在额外开销
   从你给出的代码片段来看，每次拆分列表时用了alist[:mid]来生成子列表，这会创建新的列表副本。对于百万级别的数据来说，频繁的内存分配和数据拷贝会带来巨大的性能损耗。而Timsort在设计时会尽量复用内存，减少不必要的拷贝操作。

3. 递归的累计开销
   你的实现用递归方式拆分列表，Python的递归调用本身会产生栈帧创建、销毁的开销。虽然百万级数据的递归深度仅20层左右，但累计起来也会拖慢整体速度。

优化你的归并排序的建议 #

1. 避免频繁的列表拷贝 #

改成用索引标记区间的方式，而非创建新子列表，同时用一个临时列表辅助合并，减少内存开销。示例代码：

import random
import time

def merge_sort(arr):
    temp = [0] * len(arr)  # 提前创建临时列表，避免重复分配
    
    def _merge_sort(low, high):
        if low < high:
            mid = (low + high) // 2
            _merge_sort(low, mid)
            _merge_sort(mid + 1, high)
            
            # 合并两个有序子区间
            i, j, k = low, mid + 1, low
            while i <= mid and j <= high:
                if arr[i] <= arr[j]:
                    temp[k] = arr[i]
                    i += 1
                else:
                    temp[k] = arr[j]
                    j += 1
                k += 1
            # 拷贝剩余元素
            while i <= mid:
                temp[k] = arr[i]
                i += 1
                k += 1
            while j <= high:
                temp[k] = arr[j]
                j += 1
                k += 1
            # 将临时列表的结果写回原数组
            arr[low:high+1] = temp[low:high+1]
    
    _merge_sort(0, len(arr)-1)
    return arr

2. 结合插入排序优化小片段 #

当子列表长度足够小（比如小于16），改用插入排序——插入排序在处理小规模、接近有序的数据时，性能比归并排序更优，这也是Timsort的核心优化点之一。

3. 改用迭代实现（可选） #

递归写法简洁但有栈开销，迭代版的归并排序可以避免这部分损耗，对超大数据集的性能有小幅提升。

更准确的性能测试建议 #

用timeit模块做测试，它会自动多次运行取平均值，减少单次测试的偶然性：

# 生成百万级测试数据
large_list = [random.randint(0, 1000000) for _ in range(1000000)]

# 测试自定义归并排序
def test_custom_merge():
    arr = large_list.copy()
    merge_sort(arr)

# 测试内置排序
def test_builtin_sort():
    arr = large_list.copy()
    arr.sort()

print("自定义归并排序耗时:", timeit.timeit(test_custom_merge, number=1))
print("内置排序耗时:", timeit.timeit(test_builtin_sort, number=1))

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