斯瓦内波尔的评论把我引向了here。然后，在寻找c语言的实现时，我遇到了this paper，它引用了this描述的算法。
两篇论文都描述了在O（nloglog（n））时间内运行的整数排序算法两者有什么区别？关于这个话题最近有什么发现吗？
another paper
here
最佳答案
摘自汉文摘要：
这也改善了以前的最好成绩
确定性排序算法[A。
安德逊，T.哈格鲁普，S.尼尔森，R。
拉曼，在：过程。1995年专题讨论会
计算理论（1995）427-436；
韩，X。沈，在：过程1995年
国际计算和
组合数学会议，年：讲座
计算机笔记。科学。959（1995年）
324–333]在O中排序（nloglogon）
时间但使用o（m^e）空间。我们的结果
也改善了andersson的结果
等【A.安德森，T.哈杰鲁普，S.
尼尔森，R.拉曼，in:过程1995年
计算理论研讨会
（1995）427-436]哪一类
o（nloglogon）时间和线性空间
使用随机化。
所以有两篇安德森等人的论文一个使用O（m^e）空间，另一个使用随机化，但线性空间汉文在线性空间上是确定性的。