比较排序

比较模型刻意抹去键值的数值结构，只保留“谁小于谁”的问答；算法因此必须从比较答案中辨认众多可能的相对次序。决策树的每个叶子代表一个可区分排列，二叉比较每次至多提供一 bit 分支信息，于是叶子数量的计数信息量直接给出统一下界。这个结论约束的是比较次数，不自动约束数据搬移、缓存访问或并行深度。

对三个互异元素共有 $3!=6$ 种次序，任何二叉比较决策树高度至少 $\lceil {\log }_{2}6\rceil =3$；确实存在输入需要三次比较。归并排序公理库归并排序Merge sort递归排序两半并线性合并的稳定比较排序算法。和堆排序达到 $O(n\log n)$ 最坏比较数，说明渐近下界紧确。

插入排序的最坏复杂度为 $O(n^2)$，并未达到这一界。计数排序、基数排序直接读取整数位或值域桶，因此绕过的是模型假设，而非推翻下界。存在重复键时叶子数会减少，但若算法必须处理所有互异输入，最坏下界仍保留；稳定性和原地性则是正交指标。

数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。与全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。定义可比较输入，比较排序下界公理库比较排序下界Comparison sorting lower bound任何最坏情形比较排序都需 Ω(n log n) 次比较。解释 $n\log n$ 障碍。归并排序给确定性最坏 $O(n\log n)$ 比较，随机选枢轴的快速排序公理库快速排序Quicksort围绕枢轴分区后递归排序子数组的比较排序算法。通常报告期望 $O(n\log n)$，两种界不能只因同阶就省略保证类型。若键是一字整数，超越比较的整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。会读取数位、打包字段或使用字级操作，因而已经离开本模型。

同一比较决策树视角也能区分排序与选择算法公理库选择算法Selection algorithm在未排序序列中求第 k 小元素而无需完全排序的算法族。：排序必须恢复全部相对次序，所以有 $\mathrm{\Omega }(n\log n)$ 下界；只找第 $k$ 小元素不必区分所有 $n!$ 种排列，可在比较模型中做到线性时间。把选择的界直接套给完整排序，或反过来声称任何顺序统计量都需 $n\log n$，都混淆了输出信息量。

排序成本还随机器而变。外存排序公理库外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。以块传输次数为主，最优界同时含 $N$、块大小 $B$ 和内存容量 $M$；并行算法模型公理库并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。则分别报告总工作与深度。一个算法可以保持 $O(n\log n)$ 比较工作，却在缓存传输或并行深度上很差。稳定性、原地性、移动次数和分支预测同样是正交指标，不能从“比较最优”自动推出。