插入排序为何在小数组上比快排还快？常数因子的隐藏江湖

一个经典反直觉：时间复杂度更差的插入排序，在小数组上反而比快排更快。比如 n ≤ 16 时，很多标准库会放弃快排、改用插入排序。这是为什么？

第一，常数因子碾压。"大 O"只描述增长趋势，隐藏了前面的系数。快排每步要递归调用、做分区、处理边界，单次操作的开销远大于插入排序的一行比较加移位。当 n 很小时，插入排序极小常数带来的优势，足以抵消它"更多步数"的劣势。粗略说，插入排序约 c₁·n²，快排约 c₂·n log n，若 c₁ 远小于 c₂，在 n 小处 c₁·n² 小于 c₂·n·log n 完全可能。

第二，缓存与局部性。插入排序顺序扫描、就地移位，内存访问高度连续，CPU 缓存命中率高；快排的分区与递归则会跳跃访问、产生缓存未命中。在真实硬件上，缓存友好的算法常常比"理论上更优"的算法实测更快。

第三，近乎有序时接近线性。插入排序在已部分有序的输入上只需 O(n)（逆序对少），而快排仍要完整递归。所以 introsort（C++ std::sort）和 Timsort（Python）都设了一个阈值（通常 16–32）：子数组小于阈值就切换回插入排序。这被称为"混合排序"，是理论与实践结合的典范。

这个现象给学习者的提醒是：不要只盯着大 O。真实性能 = 复杂度趋势 × 常数因子 × 硬件特性。理解插入排序的小数组优势，才算真正读懂了现代排序库的设计哲学。

图：常数因子让平方级在小 n 处反超

参考代码（Python）

用计时验证：n 很小时插入排序可能快过内置 Timsort。

import time, random
def insertion_sort(a):
    for i in range(1, len(a)):
        key=a[i]; j=i-1
        while j>=0 and a[j]>key:
            a[j+1]=a[j]; j-=1
        a[j+1]=key
    return a

a=[random.randint(0,1000) for _ in range(20)]
t1=time.perf_counter(); insertion_sort(a.copy()); t1=time.perf_counter()-t1
t2=time.perf_counter(); sorted(a); t2=time.perf_counter()-t2
print(f"n=20 插入排序 {t1:.6f}s vs 内置 {t2:.6f}s")

关联推荐

• 从冒泡到快排 — 快排为何是"平均最快"却需要收尾算法
• 算法与问题求解入门 — 建立大 O 直觉，也别被它骗
• 算法通关训练营·入门篇 — 系统理解复杂度与工程权衡