比较排序全景与 n log n 下界
一句话定义
基于「两两比较」的排序家族——插入、选择、冒泡、归并、快排、堆排序——全部无法突破 Θ(n log n) 的比较下界（决策树论证）；其中归并稳定、快排缓存友好但需随机化防退化、堆排原地但不稳定，工程排序器几乎都是三者的混合体。
为什么重要
排序是算法工程的全息缩影：同一个目标下聚集了分治、递归式、堆、稳定性、原地性、下界证明几乎所有核心概念。标准库排序为什么长成现在这样（TimSort、introsort），只有理解每个原型的取舍才能读懂。O(n log n) 下界还是你遇到的第一个「不可能性证明」——知道什么时候该放弃优化、转换假设（去 kp-021）。
前置知识
kp-002（渐进记号）、kp-003（递归式）、kp-014（堆）。
核心概念
- 插入排序：逐个把新元素插进左侧有序段；近有序数据 O(n + 逆序对数)——工程混合排序的「小数据/近有序」零件。
- 归并排序：分治 + 线性合并；稳定、O(n log n) 有保证，代价 O(n) 辅助数组；链表排序的最优选择。
- 快速排序：partition 分半 + 两侧递归；平均/期望 O(n log n)、最坏 O(n²)；随机化 pivot 或三数取中防退化；缓存局部性最佳，实践中常数最小。
- 堆排序：建堆 + n 次取顶；原地 O(n log n) 但不稳定且缓存不友好。
- 三向切分：把与 pivot 相等的元素单独分区，重复元素多时接近 O(n)。
- 稳定性：相等键保持原相对次序；多关键字排序（先次关键字再稳定排主关键字）依赖它。
- 决策树下界：n! 种排列需被区分 ⇒ 比较树至少 n! 片叶 ⇒ 高度 ≥ log₂(n!) = Θ(n log n)。
原理与机制
下界证明的机制是「把排序过程建模为决策树」：每次比较把 n! 种可能的排列空间二分，树高至少 log₂(n!)，此界对一切比较排序普适。快排的机制是「分区不变量」：扫描中始终保持「左段 < pivot ≤ 右段」，扫完 pivot 归位，递归即成立。工程混合排序的机制是扬长避短：快排主攻随机数据、递归过深转堆排保底（introsort）、小段转插入排序吃常数与局部性，近有序片段由归并识别保留（TimSort）。
直观类比
插入排序是整理扑克牌（左手牌永远有序）；归并是两摞已理好的牌轮流取小合并；快排是「先选一张基准牌把牌堆分小于/大于两堆，再各自照办」；堆排序是「先把牌架成金字塔只取最顶」。决策树下界则说：每问一句「谁大」最多二选一，要区分 n! 种可能至少要问 log₂(n!) 句。
公式或模型
- 下界：log₂(n!) ≥ log₂((n/2)^(n/2)) = Θ(n log n)（只取一半项），配合 Stirling 上界得紧确 Θ(n log n)。
- 快排期望递归式：T(n) = O(n) + E[T(k) + T(n−1−k)]，随机 pivot 下期望 T(n) = O(n log n)（期望深度 O(log n)）；最坏划分 0/n−1 时 T(n)=T(n−1)+Θ(n)=Θ(n²)。
- 插入排序与逆序对：运行时间 Θ(n + I)，I 为逆序对数——近有序时近似线性。
六算法对比表：
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 插入 | O(n²)（近有序 O(n)） | O(n²) | O(1) | ✓ |
| 归并 | O(n log n) | O(n log n) | O(n) | ✓ |
| 快排 | O(n log n) 期望 | O(n²) | O(log n) 栈 | ✗ |
| 堆排 | O(n log n) | O(n log n) | O(1) | ✗ |
| 选择 | O(n²) | O(n²) | O(1) | ✗ |
| 计数/基数（kp-021） | O(n+k)/O(d(n+k)) | 同左 | O(n+k) | ✓ |
图示
快排 partition（Lomuto，pivot=末元素）:
[3, 8, 2, 5, 1, |4|] → 扫描把 <4 的换到左侧
[3, 2, 1, |4|, 8, 5] → 4 归位，递归左右两段
决策树下界（n=3 示意）:
a<b?
/ \
b<c? a<c?
/ \ / \
abc bac acb cab… 叶子 = 一种排列，深度 = 比较次数实例或案例
- Python
sorted/Java 对象排序：TimSort = 归并 + 插入，利用现实数据的「已有序片段」（run），检测到坏Case也安全。 - C++
std::sort：introsort = 快排起步、深度超限转堆排、小段转插入排序——三种原型的混合封装。 - 为什么数据库 ORDER BY 外排用归并思想：k 路归并可流式合并已排序 run（见 kp-023）。
常见误区
- 「快排总是最快」：近有序/大量重复输入会退化，必须随机化或三向切分。
- 「O(n log n) 是一切排序的下界」：只在比较模型成立，非比较排序（kp-021）可以 O(n)。
- 忽视稳定性：多关键字排序、对象排序在非稳定排序下结果错乱且难以察觉。
- 用排序解决本可 O(n) 的问题（求最值用排序是 n log n，直接扫是 n）——先问「真的需要全序吗」。
自测题
- 证明比较排序下界 ≥ log₂(n!)，并说明为何它是 Θ(n log n)。
答案要点：n! 种排列必须各占一片叶子；高度 h 的二叉树最多 2^h 叶 ⇒ h ≥ log₂n!；Stirling n! ≈ (n/e)ⁿ ⇒ log₂n! = Θ(n log n)。
- 构造快排最坏输入（固定取首元素为 pivot）。
答案要点：已有序或逆序数组：每次划分一边为空，T(n)=T(n−1)+Θ(n)=Θ(n²)。
- 为什么链表排序首选归并而非快排？
答案要点：链表随机访问差，partition 的扫描交换不占优势；而归并只需顺序合并，O(n log n) 且稳定，辅助空间仅递归栈。
与其他知识点的关系
kp-003 主定理给出归并/快排的复杂度；kp-014 供给堆排序；kp-021 在放松「比较」假设后突破下界；kp-023 把归并思想推到外存；kp-024 的分治框架以它为头号案例。
延伸阅读
《算法导论》第 2、7、8 章；Bentley & McIlroy 1993（工业级排序函数的坑与设计）；Sedgewick《算法（第 4 版）》第 2.3 节（三向切分）。