Integer Sorting

The question

A log holds a million 32-bit integer keys, and you want them in order. Module 02 closed one door: every comparison sort needs at least $\lceil {\log }_2({10}^6)!\rceil =18,488,885$ comparisons on some input. This module sorts the same million keys in about 4.3 million steps. That does not contradict module 02, and the reason why is the first thing to understand.

Here are the twelve keys used on paper throughout the lesson, all below 1000:

Comparing is the naive approach

Merge sort puts $C$ in order with $\Theta (n\log n)$ comparisons, and module 02 proved that nothing that only compares can do much better. Look at what one comparison tells the algorithm: one bit, "left is smaller" or not. A comparison sort treats 503 as an opaque object. It never looks at the digits 5, 0, 3.

That is where it wastes work. A 32-bit key is a small integer, and a machine can use a small integer directly as a memory address. If you split a key into two 16-bit halves, one array lookup on a half sends the key to one of 65,536 slots in a single step. A single comparison, by contrast, only picks between two outcomes. The algorithms in this module use keys that way, as addresses.

The model: the word-RAM

Lower bounds are always relative to a model, so the model has to be stated. The word-RAM has a memory of $w$-bit words, where $w\ge {\log }_{2}n$ so that an index fits in a word. In one step it can add, subtract, multiply, divide with remainder, compare two words, or read or write the memory word whose address is held in a word. Cost is the number of such word operations. Keys are integers in $[0,U)$, and a key fits in one word when $U\le 2^w$.

Module 02's theorem charged one step per two-way question "is $x_i<x_j$?", so a deterministic algorithm was a binary tree with at least $n!$ leaves. Reading count[x] is not a two-way question. It jumps to one of $k$ cells in one step, a $k$-way branch. The theorem covers every algorithm that learns about keys only by comparing them, and the algorithms below are not in that class. Nothing is contradicted: the two results are about different models.

Counting sort: keys as addresses

Suppose the keys are in $[0,k)$ for a small $k$. Sort by the ones digit of $C$, so $k=10$. The algorithm has three steps:

1. Count. For each digit value $c$, count the keys whose digit is $c$.
2. Prefix sums. Turn the counts into starting positions. start[c] is the number of keys whose digit is smaller than $c$, which is exactly where the first key with digit $c$ belongs in the output.
3. Place. Scan the input from left to right. Put each key at start[c] for its digit $c$, then add 1 to start[c].

import math

C = [503, 87, 612, 245, 87, 930, 318, 764, 59, 441, 276, 805]

counts = [sum(1 for x in C if x % 10 == c) for c in range(10)]
starts = [sum(counts[:c]) for c in range(10)]
assert counts == [1, 1, 1, 1, 1, 2, 1, 2, 1, 1]
assert starts == [0, 1, 2, 3, 4, 5, 7, 8, 10, 11]

Theorem (counting sort). Counting sort is correct and stable: records with equal keys leave in the order they arrived. It uses $O(n+k)$ word operations and $O(n+k)$ extra space in the worst case.

Proof. After the prefix sums, start[c] counts the records with key below $c$, so the records with key $c$ are given the block of positions that follows all smaller keys. That makes the output sorted. Within one key, the placement scan meets the records in input order and hands them the positions start[c], start[c] + 1, … in increasing order. So equal keys keep their input order, which is stability. For the cost, clearing the counts takes $k$ steps, counting takes $n$, the prefix sums take $k$ and placing takes $n$. That is $2n+2k$ word operations, and this course's labs charge exactly that. $◻$

There is one step not to skip. The scan goes forwards and hands out increasing positions. If it went backwards it would have to hand out decreasing positions. Mixing the two, a backward scan with increasing positions, reverses every group of ties. That sort is still correct on its own, but it is useless for what comes next.

The catch is $k$. Sorting 32-bit keys directly needs a count array of $2^{32}$ cells, four thousand times larger than a million keys. To get around that, sort by pieces of the key.

One digit at a time, least significant first

Write each key in base $b$ as $d$ digits. For $C$, $b=10$ and $d=3$, and 87 is written 087. Then run a stable counting pass on the ones digit, then on the tens, and last on the hundreds. This is LSD radix sort (least significant digit first).

Look at pass 2's bracket for tens digit 0: 503 before 805. The tens pass sees two keys with the same digit and keeps them in the order pass 1 left them, and pass 1 had put them in order of their ones digit, 3 before 5. That is the whole mechanism.

The lesson checks the three rows below. Python's sorted is guaranteed stable, so here it stands in for a stable pass. The lab builds the real pass from counts.

def stable_pass(a, digit):
    return sorted(a, key=digit)          # Python's sort is stable: ties keep their order

def lsd_rows(a, b, d, order=None):
    rows = []
    for j in order or range(d):
        a = stable_pass(a, lambda x, j=j: (x // b**j) % b)
        rows.append(a)
    return rows

rows = lsd_rows(C, 10, 3)
assert rows == [[930, 441, 612, 503, 764, 245, 805, 276, 87, 87, 318, 59],
                [503, 805, 612, 318, 930, 441, 245, 59, 764, 276, 87, 87],
                [59, 87, 87, 245, 276, 318, 441, 503, 612, 764, 805, 930]]

# Tag each key with its input position: after pass 1 the two 87s (tags 1 and 4) are in input order.
tagged = sorted([(x, t) for t, x in enumerate(C)], key=lambda r: r[0] % 10)
assert [t for _, t in tagged] == [5, 9, 2, 0, 7, 3, 11, 10, 1, 4, 6, 8]

Proof, by induction on $j$. Before any pass ($j=0$) there is nothing to order, and the keys are in input order. Suppose the invariant holds after $j$ passes, and run the pass on digit $j$. Keys with different digit $j$ are put in order of that digit, because a counting pass sorts by its key. Keys with the same digit $j$ stay in the order they had, because the pass is stable, and by the induction hypothesis that is the order of their last $j$ digits. So the keys are ordered by digit $j$ first and then by the last $j$ digits, which is exactly the order of the last $j+1$ digits. Ties on all $j+1$ digits never moved, so they are still in input order. After $d$ passes the "last $d$ digits" are the whole key. $◻$

Stability is used exactly once, in the sentence "stay in the order they had", and without it the theorem is false. On the keys $[15,12]$, a pass that reverses ties gives $[12,15]$ on the ones digit (2 before 5). Then, since both tens digits are 1, it reverses them again to $[15,12]$.

The same proof sorts tuples. To order records by (field 1, field 2, …, field $r$), make stable passes on field $r$ first and field 1 last. The fields do not even need the same range: each pass is a counting sort with its own $k$.

assert lsd_rows(C, 10, 3, order=(2, 1, 0))[-1] == [930, 441, 612, 503, 764, 805, 245, 276, 87, 87, 318, 59]

Complexity, and choosing the base

Theorem (radix sort). LSD radix sort with base $b$ sorts $n$ keys in $[0,U)$ in $d=\lceil {\log }_{b}U\rceil$ counting passes (at least one), so $O(d(n+b))$ word operations in the worst case, and exactly $d(2n+2b)$ in the labs' accounting. Proof: the invariant gives correctness after $d$ passes, and the counting-sort theorem gives the cost of each pass.

The base is a trade-off. A small base means cheap passes but many of them. A large base means few passes, but each one pays $2b$ for its count array. On $C$:

With $b=1000$ there is a single pass, but the count array is 83 times the size of the input.

Take $b=n$. Then each pass costs $O(n)$ and the number of passes is $\lceil {\log }_{n}U\rceil$, so radix sort runs in $O(n\lceil {\log }_{n}U\rceil )$. When the keys are polynomially bounded, $U\le n^c$, that is $O(cn)$: linear time. And no algorithm can sort without reading all $n$ keys, so for constant $c$ this is optimal.

$b=n$ is right up to a constant factor, but it is not exactly the cheapest. For $n=4096$ random keys below $2^{36}=n^3$, the powers of two compare like this:

The cheapest is $b=512$. $b=n$ costs 1.33 times as much. The exact best base minimizes $(n+b)/\log b$, and it sits somewhat below $n$. That part is sketched here, not proved.

def digits(x, b):
    """x in base b, least significant digit first (at least one digit)."""
    out = [x % b]
    while x >= b:
        x //= b
        out.append(x % b)
    return out

def cost(n, U, b):
    d = len(digits(U - 1, b)) if U > 1 else 1
    return d, d * (2 * n + 2 * b)

assert [cost(12, 1000, b) for b in (10, 32, 1000)] == [(3, 132), (2, 176), (1, 2024)]
table = {b: cost(4096, 2**36, b) for b in (2, 16, 256, 512, 1024, 4096, 16384, 2**18)}
assert table[512] == (4, 36864) and table[4096] == (3, 49152) and table[2] == (36, 295056)
assert min(t for _, t in table.values()) == 36864 and round(49152 / 36864, 2) == 1.33

assert int(math.log(1000, 10)) == 2 and math.ceil(math.log(125, 5)) == 4
assert len(digits(999, 10)) == 3 and len(digits(124, 5)) == 3

When the passes stop paying

Return to the million keys. Every comparison sort needs 18,488,885 comparisons on some input. Radix sort with $b=2^{16}$ needs 2 passes on 32-bit keys, $2(2n+2b)=4,262,144$ steps (a comparison and a word operation are both one step). On 64-bit keys it needs 4 passes, 8,524,288 steps. Both are far below the comparison bound.

Now make the keys 128 bits wide, two words each. In base $2^{16}$ there are 8 passes costing 17,048,576 steps. Base $2^{20}$ needs 7 passes, but the count arrays make that more expensive: 28,680,064 steps. The advantage is gone. As a rule of thumb, radix sort with $b\approx n$ makes about $\log U/\log n$ passes of $O(n)$ work each, while a comparison sort pays about ${\log }_{2}n$ per key. The passes win while $\log U$ is small compared with ${\log }^{2}n$, which for keys that fit in one word and large $n$ is nearly always.

lg_fact = math.lgamma(10**6 + 1) / math.log(2)
assert math.ceil(lg_fact) == 18488885
assert cost(10**6, 2**32, 2**16) == (2, 4262144) and cost(10**6, 2**64, 2**16) == (4, 8524288)
assert cost(10**6, 2**128, 2**16) == (8, 17048576) and cost(10**6, 2**128, 2**20) == (7, 28680064)

Measure the claim

A linear bound predicts that the cost per key stays flat as $n$ grows. Take seeded random keys below $U=n^2$, run the passes, charge each pass its $2n+2b$ word operations, and divide the total by $n$:

With $b=n$ the cost is exactly $2(2n+2n)=8n$: two passes whatever $n$ is. With a fixed base 10 the cost per key grows, because the number of passes $\lceil {\log }_{10}{n}^2\rceil$ grows (6, 8, 10). "Radix sort is linear" is only true when the base grows with $n$.

import random

def measured(n, U, b, seed=451):
    rng = random.Random(seed)
    a = [rng.randrange(U) for _ in range(n)]
    d, _ = cost(n, U, b)
    ops = 0
    for j in range(d):
        ops += 2 * b                                     # clear the counts, then prefix sums
        a = stable_pass(a, lambda x, j=j: (x // b**j) % b)
        ops += 2 * n                                     # count each key, then place it
    assert a == sorted(a)
    return ops / n

assert [measured(n, n * n, n) for n in (1000, 10000, 100000)] == [8.0, 8.0, 8.0]
assert [round(measured(n, n * n, 10), 2) for n in (1000, 10000, 100000)] == [12.12, 16.02, 20.0]

A problem that looks different

A dictionary publisher must put 50,000 headwords of up to eight lowercase letters in alphabetical order, and the words have different lengths: "cab" must come before "cable", which comes before "cabled". Could anything from this lesson help, and what would you do about the short words? It is not solved here, and the lab's last problem is a different one.

Practise

In the lab you build a counting pass step by step and watch every placement keep ties in order. You predict the passes of LSD radix sort on new keys before running them, write radix sort with an exact pass count, and measure its cost per key as $n$ grows. The last problem does not say what it is.

Recap

• You can now: say which hypothesis of module 02's lower bound counting sort breaks; prove counting sort stable with $2n+2k$ word operations; prove by induction that stable passes, least significant first, sort keys and tuples; and choose a base to predict passes and cost.
• Invariant: after stable passes on the last $j$ digits (or fields), the keys are ordered by those $j$ digits, with ties in input order.
• Complexity achieved: $O(d(n+b))$ word operations with $d=\lceil {\log }_{b}U\rceil$, so $O(n\lceil {\log }_{n}U\rceil )$ with $b=n$: linear for keys below $n^c$. For a million 32-bit keys that is 4,262,144 steps, against 18,488,885 comparisons for any comparison sort on some input.
• Failure mode: an unstable pass, or passes in most-significant-first order. Each pass is correct on its own, and the result is still wrong.
• In real software: NumPy's np.sort(a, kind="stable") uses radix sort for integer types of 16 bits or less. NVIDIA CUB's cub::DeviceRadixSort is a stable GPU radix sort that processes digits from least to most significant.
• Next: module 04 uses keys as addresses when the universe is far too large for an array: hashing.

Check yourself

1. Why must every pass of LSD radix sort be stable, and which pass decides the final order?
2. With $n=1024$, the keys grow from below $n^2$ to below $n^{10}$. What happens to radix sort with $b=n$, and does it still beat comparison sorting?
3. Compare radix sort in base $2^{16}$ with merge sort on a million keys below $2^{32}$, and say what changes if you use base $2^{20}$ instead.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.