Han's Integer Sorting Algorithm

Purpose: Sort $n$ integers in $O(n\log \log n)$ deterministic time in the word RAM model, beating the $\Omega (n\log n)$ comparison lower bound by exploiting the bit structure of the keys (Yijie Han, 2002).

Why beating $n\log n$ is legal

The $\Omega (n\log n)$ bound applies to comparison-based sorting, where the only permitted operation on keys is <. Integer sorting in the word RAM model allows arithmetic, bit operations, and indexing on $w$-bit words in $O(1)$ — a strictly more powerful model, so the lower bound does not apply.

Familiar examples: counting sort is $O(n+U)$ and radix sort is $O(n\cdot w/\log n)$; neither compares keys.

The techniques

Han’s algorithm combines several word-RAM tricks:

1. Packed sorting. Fit several small keys into one machine word and sort them all with a constant number of word operations (a bitonic network implemented with masks, shifts, and one multiplication).
2. Signature sorting. Replace each key by a short hash “signature” so that many keys fit in a word; sort signatures, then repair the small number of ties.
3. Fusion trees (Fredman-Willard) — a $B$-tree with branching factor $w^{1/5}$, where each node compares against $O(w^{1/5})$ keys in $O(1)$ via a “sketch and multiply” trick. Gives $O(n\log n/\log \log n)$ sorting on its own.
4. Range reduction. Recursively halve the key length, which is where the $\log \log$ comes from.

The integer sorting landscape

Algorithm	Time	Space	Notes
Comparison sort	$\Theta (n\log n)$	$O(1)$-$O(n)$	the lower bound in its model
Counting sort	$O(n+U)$	$O(U)$	only for small key range
Radix sort (base $2^b$)	$O(n\cdot w/b)$	$O(n+2^b)$	what you actually write
Fusion trees	$O(n\log n/\log \log n)$	$O(n)$	Fredman-Willard 1993
Han	$O(n\log \log n)$	$O(n)$	deterministic
Han-Thorup	$O(n\sqrt{\log \log n})$ expected	$O(n)$	randomized; current best
Open	$O(n)$?		still unresolved

What is actually usable

None of these. But the ideas are:

• Radix sort genuinely beats std::sort by 3-5× on large arrays of 32-bit integers. An LSD radix sort with 8-bit digits is 25 lines and does four counting-sort passes. Worth having in a template library for problems with $n\ge 10^7$.
• Packing several values into one word and operating on them in parallel is the same idea as bitset optimization — a $/64$ speedup that turns $O(n^2)$ into something passable.
• Sorting by a cheap key first, then repairing ties is a useful general pattern (it is also how prefix doubling sorts suffixes).

Radix sort, concretely

void radixSort(vector<uint32_t>& a) {
    vector<uint32_t> b(a.size());
    for (int shift = 0; shift < 32; shift += 8) {
        int cnt[257] = {};
        for (uint32_t x : a) cnt[((x >> shift) & 255) + 1]++;
        for (int i = 0; i < 256; i++) cnt[i + 1] += cnt[i];
        for (uint32_t x : a) b[cnt[(x >> shift) & 255]++] = x;
        swap(a, b);
    }
}

Variants / Use Cases

• Sorting — the topic page covering every practical sort
• Fusion trees, van Emde Boas — the other word-RAM structures
• Bitset optimization — the practical form of word-level parallelism
• Complexity Theory — models of computation and why lower bounds are model-relative