algorithm - 这两种 nloglog(n) 排序算法有什么区别？ (Andersson et al., 1995 vs. Han, 2004)

Question

Swanepoel 的评论 here带我到this paper .然后，在 C 中搜索实现，我遇到了 this , 其中引用了 another paper关于描述的算法 here .

这两篇论文都描述了运行时间为 O(nloglog(n)) 的整数排序算法。两者有什么区别？最近有关于这个主题的发现吗？

Andersson et al., 1995

Han, 2004

Answer 1

摘自汉论文摘要:

This also improves previous best deterministic sorting algorithm [A. Andersson, T. Hagerup, S. Nilsson, R. Raman, in: Proc. 1995 Symposium on Theory of Computing (1995) 427–436; Y. Han, X. Shen, in: Proc. 1995 International Computing and Combinatorics Conference, in: Lecture Notes in Comput. Sci. 959 (1995) 324–333] which sorts in O(nloglogn) time but uses O(m^e) space. Our results also improves the result of Andersson et al. [A. Andersson, T. Hagerup, S. Nilsson, R. Raman, in: Proc. 1995 Symposium on Theory of Computing (1995) 427–436] which sorts in O(nloglogn) time and linear space but uses randomization.

所以有两篇 Anderson 等人的论文。一种使用 O(m^e) 空间，另一种使用随机化，但使用线性空间。汉纸是线性空间确定性的。