超越比较下界的整数排序

比较排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。每次只得到一个二元次序答案，整数算法却能一次读取多个 digit、抽取重要位或把若干键打包处理。它们突破的是信息访问模型的限制；宇宙大小、字长、允许的算术与随机化一旦改变，复杂度结论也随之改变。

边界与消歧 ​

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

Radix 正确性不变量 ​

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

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

超越比较下界依赖键的数字结构：基数排序公理库基数排序Radix sort按稳定子程序逐位处理固定长度键的非比较排序。按若干 digit 稳定分趟，计数排序公理库计数排序Counting sort对有限整数键频数计数并按前缀位置输出的线性时间非比较排序。在单趟中按有限键域计数并前缀定位。字长、基数和辅助空间决定总时间。

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

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

时间为

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

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