排序算法专题：从 TimSort 到并行排序

如果你是第一次来到这组排序文章，不建议按发布时间乱翻。排序问题的关键从来不是“哪种算法理论上更强”，而是：你的数据是什么分布、稳定性要不要、数据是否装得进内存、瓶颈在 CPU 还是 I/O、单线程还是多核。

这页的目标不是重复每篇文章的全部内容，而是把它们串成一条清晰的阅读路径。

从这里开始

如果你只想先读一篇，再决定要不要继续往下看，按这个顺序选：

1. TimSort 深度解剖：适合想理解“为什么标准库默认排序会这样设计”的读者。
2. pdqsort：适合想知道“如果不要求稳定性，现代默认排序为什么常常选它”的读者。
3. 基数排序：适合想判断“什么时候真的值得用 O(n) 排序”的读者。
4. 排序基准测试：适合已经知道算法名，但想直接看数据、做工程选型的人。

推荐阅读顺序

1. TimSort 先建立“真实数据往往部分有序”的直觉，理解 run、稳定性与工程常数因子的意义。
2. pdqsort 再看不稳定默认排序的另一条主线：模式检测、坏分区回退、对抗性输入处理。
3. 基数排序 把“比较排序”和“非比较排序”的边界真正分清楚，理解缓存与数据类型的约束。
4. 外部排序 当数据装不进内存时，CPU 复杂度不再是唯一问题，I/O 模型开始主导性能。
5. 并行排序 进入多核与 GPU 时代，同一个排序问题需要重新看待同步、分片和吞吐。
6. 排序基准测试 最后回到统一测试框架，用数据校验前面的直觉，而不是靠经验拍脑袋。

按问题找文章

一页结论

• 如果你要的是稳定排序，而且数据常常部分有序，优先看 TimSort。
• 如果你要的是通用内存内排序吞吐，且不要求稳定性，优先看 pdqsort。
• 如果键提取便宜、位宽固定、数据规模足够大，再考虑 基数排序。
• 如果数据已经不在内存里，直接跳去 外部排序。
• 如果瓶颈已经从单核 CPU 变成并行吞吐，再看 并行排序。
• 如果你要把选型说服给别人，最后拿 排序基准测试 的实测数据收尾。

延伸阅读

• SIMD 算法设计模式：排序优化里绕不开的向量化直觉。
• 缓存无关算法：理解内存层级为什么会改变算法优先级。
• B-tree 深度解剖：当排序与外存、索引结构联系起来时，这篇很有帮助。