超越比较下界的整数排序

模型分界 ​

比较决策树只能询问两个键的次序，因 $n!$ 种排列得到 $\mathrm{\Omega }(n\log n)$ 比较下界。若键是 $w$ 位整数、可在 Word-RAM 中按位提取和算术，算法获得比较之外的信息，下界不再适用。复杂度必须同时写 $n$、宇宙 $U\le 2^w$、额外空间以及期望或确定保证。

基线算法 ​

Counting sort 用 $U$ 个桶，时间和空间 $O(n+U)$。Radix sort 每趟处理 $b$ 位，以稳定 counting sort 为子程序；趟数 $d=\lceil w/b\rceil$，时间

$$O(d(n+2^b)).$$

32 位无符号整数按字节处理时做四趟、每趟 256 个桶，这是固定机器字段上的真实工程方案；渐近分析中不能因此把随 $n$ 增长的任意 $w$ 宣布成常数。

更高级的突破 ​

当 $U$ 太大不能开桶时，可先用字级并行找重要位、用哈希把键分到受控桶，再递归排序。历史最优界随 Word-RAM 操作集、随机化与空间约束变化；本页强调机制，不把某篇论文的复杂表达式当作跨模型永久“最优”。

边界与消歧 ​

超长大整数可能跨多个机器字，位提取不再 $O(1)$；带昂贵比较器的对象也不是整数键。稳定性决定相同键记录的相对顺序，radix 每趟若不稳定会破坏结果。随机哈希算法还需报告失败概率或 Las Vegas 重试。比较下界公理库比较排序下界Comparison sorting lower bound任何最坏情形比较排序都需 Ω(n log n) 次比较。仍完全正确，只是它约束的模型更弱。

Radix 正确性不变量 ​

最低有效位优先排序在第 $j$ 趟后，记录按最低 $jb$ 位稳定有序。下一趟按更高 digit 稳定分桶：不同新 digit 决定主次序，相同 digit 内保留此前低位次序，归纳得到全键排序。若子排序不稳定，相同高 digit 的记录会打乱已排低位，最终不一定有序。

最高有效位优先 radix 则递归各桶，不依赖同一稳定性不变量，但递归栈、空桶和短键终止条件不同。两类都使用 digit，不应只报“$d$ 趟”而省略方向和稳定要求。

四趟字节排序的完整不变量 ​

对 32 位无符号键、基数 $b=256$，从最低字节到最高字节做四趟稳定 counting sort。第 $j$ 趟结束后，数组按低 $8j$ 位有序；下一趟对第 $j+1$ 个字节分桶时，稳定性保持同桶元素原有低位次序，因此归纳得到按完整 32 位有序。

时间为

$$O(d(n+b))=O(4(n+256)),$$

额外空间为 $O(n+b)$。有符号二补码需要在最高字节调整符号桶次序，浮点键更不能直接沿用整数序。若键是任意精度整数，读取键本身就可能超过一个字操作，$w=\mathrm{\Theta }(\log n)$ 的模型假设也不成立。

更快的理论结果常使用乘法、打包、哈希或随机化，并把 $w$、$U$、空间和成功保证写入界。它们说明比较下界不适用，而不是说明任何“整数类型”都应承诺线性最坏时间。

参考资料

• Yijie Han, Mikkel Thorup, Integer Sorting in O(n√log log n) Expected Time and Linear Space, FOCS, 2002.
• Arne Andersson et al., Sorting in Linear Time?, STOC, 1995.
• Cormen et al., Introduction to Algorithms, counting and radix sorting.