What is the difference between these two nloglog(n) sorting algorithms? (Andersson et al., 1995 vs. Han, 2004)

Question

Swanepoel's comment here lead me to this paper. Then, searching for an implementation in C, I came across this, which referenced another paper on an algorithm described here.

Both papers describe integer sorting algorithms that run in O(nloglog(n)) time. What is the difference between the two? Have there been any more recent findings about this topic?

Andersson et al., 1995

Han, 2004

Answer 1

From the abstract of the Han Paper:

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.

So there are two Anderson et al papers. One uses O(m^e) space and other uses randomization, but linear space. Han paper is deterministic with linear space.