Han–Thorup Integer Sorting Algorithm

The Han–Thorup Integer Sorting Algorithm is a randomized algorithm presented by Yijie Han and Mikkel Thorup at the 2002 IEEE Symposium on Foundations of Computer Science that sorts n integers, each fitting in a machine word, in O(n √(log log n)) expected time using linear space. It is the fastest known bound for sorting integers on the word RAM when the word length w is unrestricted relative to n. The result sits between the O(n log n) bound that governs comparison sorting and the long-standing open question of whether integers can be sorted in linear time on a general word RAM. It also illustrates how the interplay of hashing, word-level parallelism, and recursive reduction of key length can beat the information-theoretic barrier that applies to comparison-based methods.

Comparison sorting needs Ω(n log n) comparisons because there are n! possible orderings and each comparison yields one bit. Real machines, however, can manipulate keys as binary numbers. The word RAM model formalizes this: memory consists of words of w bits, and arithmetic, bitwise operations, shifts, and indexing take unit time. Keys are w-bit integers, and the word length satisfies w ≥ log n so that every address fits in a word.

In this model radix sort sorts n keys of w bits in O(n · w / log n) time by processing log n bits per pass, which is linear if w = O(log n). When w is larger, for instance w = log² n, radix sort degrades to O(n log n) and offers no advantage. The question then is how fast sorting can be as a function of n alone when w is arbitrary. The answer depends on a progression of results, each shaving the exponent of the logarithm.

Fredman and Willard's 1993 fusion trees introduced the central idea of packing several keys into one word and comparing them in parallel. A fusion node holds w^1/5 keys and finds a query's rank among them in constant time, giving sorting in O(n log n / log log n) time, the first non-comparison bound independent of w. Their paper was the first demonstration that the Ω(n log n) barrier can be broken for every word length.

Andersson, Hagerup, Nilsson, and Raman (1998) then showed that with a clever use of packed keys, sorting could be done in O(n log log n) expected time. Their "Sorting in linear time?" paper established the technique of reducing key length by hashing and then sorting the reduced keys in packed form. Kirkpatrick and Reisch's much earlier work, summarized in Kirkpatrick–Reisch sort, had already established the recursive reduction principle: halving the key length in each recursion level gives a time of O(n log(w / log n)), which is far better than radix sort for long keys.

Thorup then gave deterministic bounds of O((log log n)²) time per key in linear space, which Han progressively sharpened to a deterministic O(n log log n) algorithm. The Han–Thorup result improves on these in the randomized case, replacing the log log n factor with its square root.

The algorithm combines three ideas.

Signature sorting. Long keys are compressed to short signatures using a hash function. Splitting each key into pieces and hashing each piece to O(log n) bits yields a signature that preserves distinctness with high probability. Sorting the signatures, rather than the original keys, reduces the problem to short keys, after which the order of the original keys is recovered by comparing against a reduced structure. The randomized hashing step is the source of the expected, not worst-case, time bound. The scheme resembles other applications of randomized hashing, such as cuckoo hashing, in which careful analysis of a short hash code supports constant-time operations.

Packed sorting. When keys are short compared to the word length, many of them fit in one word. Using a network of word-parallel comparisons and bit-vector tricks, multiple keys can be merged and compared in a single instruction. If k keys of length ℓ fit in a word, packed merging sorts them with operations proportional to the number of words instead of the number of keys.

Recursive reduction. The two tools alternate. A set of n keys with word length w is mapped to signatures of length w' much smaller than w, packed, and sorted by a recursive call. The cost per level depends on how much the key length shrinks. Han and Thorup balance parameters so that the cost of packing and merging at each level is dominated by a term that depends on √(log log n), and the recursion terminates after a number of levels whose total contribution is O(√(log log n)) amortized per key.

The bound is stated as an expected running time because of the hash step, and the space is O(n) words. Han and Thorup also gave a deterministic version at a cost of O(n log log n), matching the best known deterministic sort at that time.

Radix sort wins when w = O(log n), the usual situation for integer keys of 32 or 64 bits with arrays of millions of items. The Han–Thorup algorithm is not used in production: the constant factors, the need for hashing, and the intricate packed arithmetic make it slower in practice than a well-tuned radix sort for realistic inputs. Its value is theoretical, locating the true complexity of integer sorting.

No super-linear lower bound for integer sorting on the word RAM is known. Because sorting requires at least reading the input, the best possible bound is Ω(n), and it remains unknown whether O(n) is achievable for all word lengths. Known results show O(n) time when w = O(log n) via radix sort, and O(n) when w is at least about log^2+ε n via a different packed approach (Andersson et al. reach linear expected time for keys of length at least (log n)^2+ε, because signature reduction becomes powerful enough to cancel the overhead). The intermediate range between log n and log^2+ε n is the difficult region where the √(log log n) factor appears.

Lower bounds in restricted models complicate the picture. In cell-probe models for related problems, such as predecessor search, Pătrașcu and Thorup proved tight bounds that depend on n, w, and space, which indicate that the algorithmic ingredients used for sorting are close to optimal for data structures. Whether those bounds translate into a lower bound for sorting remains open, in part because sorting can amortize cost across all keys and does not need each key to be located independently. The relation between sorting and computational complexity theory more generally shows how model details, here the word length, determine the exact complexity classification of a basic task.

Integer sorting is a prototype of problems where model choice changes the answer. The Han–Thorup algorithm demonstrates that three techniques, hashing for length reduction, word-level parallelism for packing, and recursion for balancing, can compose into an algorithm with a surprising bound. It also stimulated work on priority queues, since an integer sorting algorithm with O(n f(n)) time yields a priority queue with O(f(n)) amortized cost per operation via the standard equivalence. Han and Thorup's result thus gives a randomized priority queue with O(√(log log n)) expected time per operation, which directly improves algorithms for shortest paths and minimum spanning trees on the word RAM.

1. Han, Y., & Thorup, M. (2002). Integer sorting in O(n √(log log n)) expected time and linear space. Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), 135–144. https://doi.org/10.1109/SFCS.2002.1181890
2. Fredman, M. L., & Willard, D. E. (1993). Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3), 424–436. https://doi.org/10.1016/0022-0000(93)90040-490040-4)
3. Andersson, A., Hagerup, T., Nilsson, S., & Raman, R. (1998). Sorting in linear time? Journal of Computer and System Sciences, 57(1), 74–93. https://doi.org/10.1006/jcss.1998.1580
4. Kirkpatrick, D., & Reisch, S. (1984). Upper bounds for sorting integers on random access machines. Theoretical Computer Science, 28(3), 263–276. https://doi.org/10.1016/0304-3975(83)90023-390023-3)
5. Han, Y. (2004). Deterministic sorting in O(n log log n) time and linear space. Journal of Algorithms, 50(1), 96–105. https://doi.org/10.1016/j.jalgor.2003.09.001