Non-Comparison Sorts & the Lower Bound
Every sort in this module so far — insertion, merge, quick, heap — learns about its input only by asking "is ?". This lesson proves that any algorithm restricted to such questions needs at least of them in the worst case, about , so merge sort and heap sort are optimal up to a constant factor. Then it breaks the bound — not by cleverness inside the comparison model, but by leaving it. If keys are small integers, or strings of digits, or uniformly distributed reals, you can use the key itself as an address, and a single array write tells you more than a comparison ever could. Counting sort, radix sort and bucket sort do exactly that, and they run in linear time on the inputs they are built for. Knowing both halves — why is a wall and how to walk around it — is what lets you decide, for a real dataset, which side of the wall you are on.
Lesson position: Module 2 · Searching & Sorting · previous: Heap Sort · next: Sorting in the Real World · course map.
Why this exists
The oldest automatic sorting machines were not comparison sorts at all. Herman Hollerith's punched-card equipment, introduced for the 1890 US census, and the electric card sorters that followed it for most of the twentieth century sorted cards one column at a time: the machine dropped each card into one of ten pockets according to the digit punched in the current column, the operator stacked the pockets in order, and the deck went through again for the next column. Operators learned to start with the least significant column, because then each pass kept the order established by the previous passes. That procedure is LSD radix sort, and it predates electronic computers. When computers arrived, Harold Seward's 1954 MIT thesis is usually credited with formulating radix sort and counting sort for them.
Meanwhile, the theory of comparison sorting matured. The decision-tree argument — any comparison sort is a binary tree of questions with at least leaves, so it must be at least deep — is folklore by the 1950s and appears in every algorithms textbook (CLRS §8.1, Knuth Vol. 3 §5.3.1). It explains why decades of work on comparison sorts converged on , and it says precisely what you must give up to go faster: the comparison model.
Non-comparison sorts are not museum pieces. Radix sort is the standard way to sort large arrays of keys on GPUs (NVIDIA's CUB and Thrust libraries), because it maps onto thousands of threads far better than comparison sorts do. Suffix-array construction, the backbone of full-text indexes and genome aligners, is built from repeated radix sorts of integer ranks. Database engines sort on normalized binary keys with radix sort (DuckDB) or accelerate comparison sorts with fixed-size "abbreviated" key prefixes (PostgreSQL). Counting sort is how a compressed sparse row graph is built, how histogram equalisation works, and how a "sort colors" interview question is solved in two passes. This lesson gives you the proofs and the engineering to use them well.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| Keys are integers in a small known range ( with ): ages, grades, ASCII, colours | Counting sort, |
| "sort by one field, preserving the order of equal elements" with small integer keys | Stable counting sort |
| Fixed-width integers (32/64-bit), very large , no custom comparator | LSD radix sort, |
| Strings / variable-length keys, lexicographic order, many shared prefixes | MSD radix sort or 3-way radix quicksort |
| Reals uniformly distributed in a known interval | Bucket sort, expected |
| "maximum gap between sorted neighbours in linear time" | Pigeonhole buckets (bucket sort idea) |
| "top k frequent", "sort by frequency" | Bucket by count: counts are in |
| "prove you cannot do better than ", "lower bound" | Decision tree: |
| Arbitrary comparator, locale collation, objects with no numeric key | Comparison sort — no direct radix key exists |
| Range (e.g., 64-bit IDs, ) | Comparison sort, or radix with few passes; counting sort's is fatal |
Intuition & first principles
What a comparison tells you
A comparison has two outcomes, so it yields at most one bit of information. A sorting algorithm must distinguish between all possible orderings of its input, because each one requires a different rearrangement. Identifying one of possibilities needs bits. So: at least comparisons. That is the entire lower bound in one paragraph; the next section makes it rigorous.
What an array write tells you
Now suppose the keys are integers in . Allocate counters and, for each element, increment count[key]. One memory operation has just "compared" the key against all possible values at once — it has extracted bits, not one. After one pass the counts say exactly how many of each value there are, and a prefix sum turns counts into final positions. No two keys were ever compared. The price is that the algorithm now depends on what the keys are: it must be possible to use a key as an array index. That is the trade every non-comparison sort makes.
Radix sort extends the idea to keys too large to index directly: split a -bit key into digits of bits, and counting-sort by one digit at a time, using counters per pass. Bucket sort extends it to real numbers: if keys are spread evenly over , then floor(key * n) is an approximate final position, and the leftover work inside each bucket is tiny on average.
Mechanics
The decision-tree lower bound
Model any deterministic comparison sort on inputs of size as a decision tree: each internal node is a comparison ?, its two subtrees are what the algorithm does next for each answer, and each leaf is the permutation the algorithm outputs. Running the algorithm on an input traces one root-to-leaf path; the number of comparisons is the path length. For :
flowchart TD
R{"a1 <= a2 ?"} -->|"yes"| L{"a2 <= a3 ?"}
R -->|"no"| RR{"a1 <= a3 ?"}
L -->|"yes"| P1["a1, a2, a3"]
L -->|"no"| LR{"a1 <= a3 ?"}
LR -->|"yes"| P2["a1, a3, a2"]
LR -->|"no"| P3["a3, a1, a2"]
RR -->|"yes"| P4["a2, a1, a3"]
RR -->|"no"| RRR{"a2 <= a3 ?"}
RRR -->|"yes"| P5["a2, a3, a1"]
RRR -->|"no"| P6["a3, a2, a1"]
Six leaves, one per permutation; height 3; and , so this tree (insertion sort's) is optimal.
Theorem. Every comparison sort makes at least comparisons on some input of size .
Proof. A correct algorithm must reach a different leaf for each of the orderings of distinct keys: if two different orderings reached the same leaf, the algorithm would apply the same rearrangement to both and at least one output would be unsorted. So the tree has at least leaves. A binary tree of height has at most leaves. Hence , i.e. , and since is an integer, . The height is the worst-case number of comparisons. ∎
The same argument bounds the average case: a binary tree with leaves has average leaf depth at least (balanced trees minimise it), so even averaged over all inputs, a comparison sort needs comparisons. Randomization does not help either: a randomized comparison sort is a probability distribution over decision trees, and each tree needs that many on average.
How big is ? Stirling's approximation gives
The leading term is , so the bound is . A cruder but self-contained argument: (the top half of the factors are each at least ), so . Computed values (script-verified; "Stirling" is the three-term formula):
| n | n! | log2(n!) | ⌈log2(n!)⌉ | Stirling |
|---|---|---|---|---|
| 3 | 6 | 2.58 | 3 | 2.55 |
| 4 | 24 | 4.58 | 5 | 4.55 |
| 5 | 120 | 6.91 | 7 | 6.88 |
| 6 | 720 | 9.49 | 10 | 9.47 |
| 8 | 40,320 | 15.30 | 16 | 15.28 |
| 10 | 3,628,800 | 21.79 | 22 | 21.78 |
| 12 | 479,001,600 | 28.84 | 29 | 28.83 |
| 16 | 20,922,789,888,000 | 44.25 | 45 | 44.24 |
| 20 | 2,432,902,008,176,640,000 | 61.08 | 62 | 61.07 |
Three things to notice. Stirling is accurate to 0.03 even at . For large the bound sits well below : at , against (ratio 0.93). And the bound is not always achievable: Ford and Johnson's merge-insertion algorithm meets exactly for , but the minimum for is 30 comparisons, one more than the bound of 29 (Wells, 1965; see Knuth Vol. 3 §5.3.1). Merge sort's worst case, , is with between about 0.91 and 1, so it exceeds the bound only by a linear term of roughly – — the sense in which merge sort is "comparison-optimal".
Counting sort (stable, prefix-sum version)
Input: keys in . Output: a new array, sorted, with equal keys in their original relative order.
count = [0] * (k + 1)
for x in a: count[x] += 1 # histogram
for v in 1..k: count[v] += count[v - 1] # count[v] = number of keys <= v
for j = n-1 down to 0: # right-to-left scan
count[a[j]] -= 1
out[count[a[j]]] = a[j]
After the prefix sum, count[v] is one past the last output slot that key may occupy, so the slots for key are [count[v-1], count[v]). Scanning the input right to left and filling each key's block from its right end places the last occurrence of each key last, the second-to-last occurrence second-to-last, and so on. That is stability. An equivalent formulation computes exclusive prefix sums (the first slot of each key) and scans left to right, filling blocks from the left; both are stable. Scanning left to right with the inclusive sums, a common bug, reverses every group of equal keys.
flowchart LR
A["input a, n keys"] -->|"pass 1: histogram"| B["count of each value 0..k"]
B -->|"pass 2: prefix sums"| C["count of v = number of keys <= v"]
C -->|"pass 3: right to left, decrement then place"| D["stable sorted output"]
Trace on the CLRS example a = [2, 5, 3, 0, 2, 3, 0, 3], (computed by script; "." is an empty output slot):
| Step | Phase | j | a[j] | count[0..5] after | out after |
|---|---|---|---|---|---|
| 1 | histogram | — | — | [2, 0, 2, 3, 0, 1] | . . . . . . . . |
| 2 | prefix sums | — | — | [2, 2, 4, 7, 7, 8] | . . . . . . . . |
| 3 | place | 7 | 3 | [2, 2, 4, 6, 7, 8] | . . . . . . 3 . |
| 4 | place | 6 | 0 | [1, 2, 4, 6, 7, 8] | . 0 . . . . 3 . |
| 5 | place | 5 | 3 | [1, 2, 4, 5, 7, 8] | . 0 . . . 3 3 . |
| 6 | place | 4 | 2 | [1, 2, 3, 5, 7, 8] | . 0 . 2 . 3 3 . |
| 7 | place | 3 | 0 | [0, 2, 3, 5, 7, 8] | 0 0 . 2 . 3 3 . |
| 8 | place | 2 | 3 | [0, 2, 3, 4, 7, 8] | 0 0 . 2 3 3 3 . |
| 9 | place | 1 | 5 | [0, 2, 3, 4, 7, 7] | 0 0 . 2 3 3 3 5 |
| 10 | place | 0 | 2 | [0, 2, 2, 4, 7, 7] | 0 0 2 2 3 3 3 5 |
The three 3s (input positions 2, 5, 7) land in slots 4, 5, 6 in that order: position 7 went to slot 6 first, then position 5 to slot 5, then position 2 to slot 4. At the end, count[v] holds the first slot of each key — the exclusive prefix sums — a free by-product some algorithms use.
LSD radix sort
Write each key in base (in practice or , so a digit is a byte or an 11-bit field). Sort the whole array by the least significant digit with a stable counting sort, then by the next digit, and so on up to the most significant. Trace on [170, 45, 75, 90, 802, 24, 2, 66] in base 10 (computed by script):
| Pass | Digit sorted on | Array after the pass |
|---|---|---|
| 0 | — | [170, 45, 75, 90, 802, 24, 2, 66] |
| 1 | ones | [170, 90, 802, 2, 24, 45, 75, 66] |
| 2 | tens | [802, 2, 24, 45, 66, 170, 75, 90] |
| 3 | hundreds | [2, 24, 45, 66, 75, 90, 170, 802] |
Look at pass 2: 802 and 2 both have tens digit 0, so stability keeps them in the order pass 1 left them (802 before 2). That is wrong for the final answer, but pass 3 fixes it because their hundreds digits differ. Now look at 170 and 75: both have tens digit 7, so pass 2 keeps 170 before 75; pass 3 again separates them by the hundreds digit (1 vs 0). And 45 and 24, which differ at the tens digit, are put in the right order by pass 2 and never disturbed again, because pass 3 sees equal hundreds digits (0) and stability preserves the order. The invariant that makes this work is proved in Correctness: after pass , the array is sorted by the last digits.
MSD radix sort
MSD radix sort goes the other way: partition by the most significant digit into buckets, then recursively sort each bucket on the next digit. Buckets never mix again, so — unlike LSD — later passes do not need stability across buckets, and the recursion can stop as soon as a bucket has one element or its keys are exhausted. That makes MSD natural for strings of varying length (a string that ends sorts before all its extensions) and lets it skip shared prefixes cheaply. Its weaknesses are the opposite of LSD's: deep recursion on long common prefixes, and enormous overhead from mostly-empty buckets once subarrays get small, so practical MSD sorts switch to insertion sort below a few dozen elements.
flowchart TD
A["strings: sea, she, sell, by, the, shell, shore"] -->|"1st char"| B["b: by"]
A -->|"1st char"| C["s: sea, she, sell, shell, shore"]
A -->|"1st char"| D["t: the"]
C -->|"2nd char"| E["e: sea, sell"]
C -->|"2nd char"| F["h: she, shell, shore"]
F -->|"3rd char"| G["e: she, shell"]
F -->|"3rd char"| H["o: shore"]
G -->|"4th char"| I["end: she"]
G -->|"4th char"| J["l: shell"]
American flag sort (McIlroy, Bostic and McIlroy, "Engineering Radix Sort", Computing Systems, 1993) is the in-place MSD variant: count the bucket sizes, compute bucket boundaries, then permute elements into their buckets by cycle-chasing swaps, with no output array. It is not stable but needs only extra space per recursion level. Three-way radix quicksort (Bentley and Sedgewick, 1997) is the comparison-flavoured cousin: partition on one character into less / equal / greater, recursing on the next character only in the equal part — it adapts well to strings with long shared prefixes.
Choosing the radix
For -bit keys and digits of bits, LSD radix sort makes passes, each costing : a counting pass plus a scatter pass over the data, and a scan of counters. Total work . Larger means fewer passes but larger count arrays:
| Bits per digit | Passes for 32-bit keys | Counters per pass | Count array size (4-byte counters) |
|---|---|---|---|
| 1 | 32 | 2 | 8 B |
| 4 | 8 | 16 | 64 B |
| 8 | 4 | 256 | 1 KB |
| 11 | 3 | 2,048 | 8 KB |
| 16 | 2 | 65,536 | 256 KB |
CLRS (Lemma 8.4) shows that choosing minimises asymptotically, giving : for and 32-bit keys, two 16-bit passes. Hardware changes the answer. Each scatter pass writes to different output locations at once; with much larger than the number of cache lines and TLB entries the CPU can keep "open", every write misses. That is why CPU radix sorts almost always use (four passes, a 1 KB histogram that sits in L1) or (three passes for 32-bit keys, a classic choice for floats). A common trick computes all histograms in one initial read of the data, then does the scatter passes, saving reads. Another skips a pass entirely when its histogram shows every key has the same digit — frequent in practice because real 64-bit keys rarely use all 64 bits.
Signed integers and floats need a key transformation so that unsigned digit order matches numeric order. For two's-complement signed integers, flip the sign bit (x ^ 0x80000000 for 32-bit), which maps monotonically onto . For IEEE 754 floats, reinterpret the bits as an unsigned integer, then flip all bits if the sign bit is set and only the sign bit otherwise; that orders negatives correctly (larger magnitude = smaller) and puts them below positives. NaNs need a policy.
Bucket sort
Input: reals drawn independently and uniformly from . Create empty buckets; put into bucket ; sort each bucket with insertion sort; concatenate. Each bucket covers an interval of width , so bucket 's elements are all smaller than bucket 's, and concatenation is sorted. Expected running time: , proved in Complexity. On non-uniform data the buckets can be very unequal — all keys in one bucket gives insertion sort's — so bucket sort is only as good as your knowledge of the distribution. In practice you often use sample-based splitters instead of fixed intervals: sort a random sample, take every -th value as a bucket boundary, and the buckets come out balanced for any distribution. That idea, samplesort, is the basis of many parallel and distributed sorts (each machine receives one bucket).
The ladder: brute force → better → optimal
The ladder here is for a concrete task: sort 32-bit integers.
Rung 1 — comparison sort. std::sort / introsort: about comparisons with unpredictable branches. Optimal within the comparison model, by the theorem above.
Rung 2 — counting sort. If the values are known to lie in a small range, say , one histogram pass and one output pass: operations, about 14× fewer than rung 1. But for arbitrary 32-bit values : a 16 GB count array. Counting sort alone fails the general task.
Rung 3 — LSD radix sort with bytes. Four stable counting passes on 8-bit digits: about element reads and writes plus counter work, independent of the value range. Linear in with a small constant, but it needs an buffer and its scatter writes are cache-unfriendly when the array is large.
Rung 4 — tuned radix sort. One read to build all four histograms, skip passes whose digit is constant, 11-bit digits for three passes, software write-combining buffers to tame the scatter. This is the territory of production libraries (and of GPU radix sorts, which add per-block histograms and prefix sums across thousands of threads).
| Rung | Time | Extra space | Needs | Fails when |
|---|---|---|---|---|
| Comparison sort | only a comparator | — (always works) | ||
| Counting sort | integer keys in | |||
| LSD radix (8-bit) | fixed-width integer keys | tiny , wide keys, custom orders | ||
| Bucket sort | expected | known, roughly uniform distribution | skewed data |
Correctness
Counting sort is correct and stable
Claim. The output is sorted, is a permutation of the input, and equal keys appear in the same relative order as in the input.
Proof. After the prefix-sum pass, . Let (with ) and ; the interval has exactly as many slots as there are copies of , and the intervals for tile in increasing order of . In the placement pass, every element with key decrements and writes to the new value, so the copies of fill , each slot exactly once. Hence the output is a permutation and every key lands in its own value's interval: sorted.
Stability. The scan visits input positions in decreasing order among the copies of , and assigns them decreasing slots . So for two copies at input positions , is visited first and receives the larger slot: ends up before . ∎
LSD radix sort is correct
Claim. After the pass on digit (counting from the least significant, ), the array is sorted by the key formed by the last digits. After passes it is sorted.
Proof by induction on . For the array was counting-sorted by digit 1, so it is sorted by the last one digit. Assume it is sorted by the last digits before pass . Take any two keys and and compare them by their last digits. If their -th digits differ, pass orders them by that digit, which is the most significant of the digits, so the order is right regardless of the lower digits. If their -th digits are equal, pass — being stable — keeps them in the order they had before, which by the induction hypothesis is the order of their last digits, and that is the correct order for the last digits since the -th digits tie. Either way and end up correctly ordered. ∎
The proof uses stability in exactly one place, and that place is essential: with an unstable digit sort, LSD radix sort is simply wrong. (Try sorting [21, 12] by tens then ones with a digit sort that reverses ties.)
MSD radix and bucket sort
MSD radix sort is correct by strong induction on the number of remaining digits: the first-digit partition puts every key in a bucket whose keys all precede those of the next bucket, and each bucket is sorted recursively. Bucket sort is correct because bucket holds exactly the keys in , buckets are concatenated in order, and each bucket is sorted.
Complexity
Counting and radix sort
- Counting sort: time — two passes over the input, one over the counts — and extra space for the counts and the output. Linear when .
- LSD radix sort: passes of counting sort with base : time, extra space. For -bit keys and -bit digits, and . With , ; for — keys polynomial in — that is .
- MSD radix sort: where is the average length of the distinguishing prefix — it reads only as many characters as needed to tell keys apart. For random strings that is about characters per key.
Is linear time "breaking" the lower bound? No: the theorem only covers algorithms whose sole access to keys is comparison. Radix sort reads key bits. In the word-RAM model, where keys are -bit integers, the best known deterministic integer sorting runs in time (Han, 2002), and randomized (Han and Thorup, 2002); whether is possible for all is open.
Bucket sort: expected O(n) under uniform input
Let be the number of keys in bucket . Insertion sort on bucket costs , so the expected total cost is . Each key lands in bucket independently with probability , so with and . Therefore
and . Total expected cost: . A simulation with over 2,000 trials gave an average of 1,998.8, against the predicted 1,999. The argument needs only that each key's bucket is uniform and independent — not that keys are uniform reals — which is why it also applies to hashed keys. Note what it does not give: a worst-case bound. One unlucky or adversarial input puts everything in one bucket.
When non-comparison sorts lose
- Large key range. Counting sort's dominates when ; sorting 1,000 64-bit IDs with counting sort is absurd. Radix sort handles wide keys, but with passes of each it loses to an sort when is small: for 64-bit keys, eight byte-passes each read and write every element (about memory operations plus counter updates), against roughly comparisons for a comparison sort.
- Memory. LSD radix sort and counting sort need an output buffer; in-place MSD variants (American flag sort) give up stability.
- Keys that are not integers. Floats need the bit transformation above; strings need MSD processing; composite keys need packing into a byte string whose unsigned order equals the desired order (a normalized or binary-comparable key). Arbitrary comparators — locale-aware collation, "sort by distance from a moving point", user-defined orderings — have no such key at all, unless you can compute one (C's
strxfrmtransforms a string into a key whosestrcmporder matches the locale's collation, at a cost in size). - Cache and TLB behaviour. Each LSD pass reads sequentially but scatters writes across destinations. On large arrays this can make radix sort memory-bandwidth-bound, and its theoretical advantage over a cache-friendly comparison sort narrows to a small constant factor. Libraries such as pdqsort and Timsort are often competitive on real CPUs for this reason, and they handle any comparator.
- Skewed data for bucket sort. Real data is rarely uniform; fixed-width buckets need a known distribution or sampled splitters.
- Stability requirements for MSD in place. In-place MSD radix sorts are not stable; stable MSD needs a buffer.
Implementation
Canonical code: stable counting sort (with an offset, so negative keys work), a counting sort that returns the stable permutation (the form you use to sort records by a key), LSD radix sort on 32-bit signed integers with four 8-bit passes and the sign-bit flip, and bucket sort for reals in . All four blocks run the same tests: the CLRS counting example and its permutation, the LSD example, 2,000 signed values in and the extremes for radix sort, 2,000 values in for counting sort, 2,000 reals for bucket sort (MINSTD generator ), and a stability check on 2,000 keys in .
def counting_sort(a: list[int]) -> list[int]:
"""Stable counting sort of integers; O(n + k) with k = max - min."""
if not a:
return []
lo, hi = min(a), max(a)
count = [0] * (hi - lo + 1)
for x in a:
count[x - lo] += 1
for v in range(1, len(count)):
count[v] += count[v - 1] # count[v] = number of keys <= v + lo
out = [0] * len(a)
for x in reversed(a): # right to left keeps equal keys in order
count[x - lo] -= 1
out[count[x - lo]] = x
return out
def counting_sort_indices(keys: list[int], k: int) -> list[int]:
"""Stable permutation p with keys[p[0]] <= keys[p[1]] <= ...; keys in 0..k.
Exclusive prefix sums, left-to-right scan."""
start = [0] * (k + 1)
for x in keys:
start[x] += 1
total = 0
for v in range(k + 1):
start[v], total = total, total + start[v] # first slot for key v
p = [0] * len(keys)
for j, x in enumerate(keys):
p[start[x]] = j
start[x] += 1
return p
def radix_sort_lsd(a: list[int]) -> list[int]:
"""32-bit signed integers: 4 stable passes on 8-bit digits of (x + 2^31),
which equals x with its sign bit flipped."""
src = list(a)
for shift in range(0, 32, 8):
count = [0] * 257
for x in src:
count[(((x + 2**31) >> shift) & 255) + 1] += 1
for d in range(256):
count[d + 1] += count[d] # count[d] = first slot for digit d
dst = [0] * len(src)
for x in src:
d = ((x + 2**31) >> shift) & 255
dst[count[d]] = x
count[d] += 1
src = dst
return src
def bucket_sort(a: list[float]) -> list[float]:
"""Reals in [0, 1): n buckets, insertion sort inside each. Expected O(n) if uniform."""
n = len(a)
buckets: list[list[float]] = [[] for _ in range(n)]
for x in a:
buckets[int(x * n)].append(x)
out: list[float] = []
for b in buckets:
for i in range(1, len(b)): # insertion sort
x, j = b[i], i - 1
while j >= 0 and b[j] > x:
b[j + 1] = b[j]
j -= 1
b[j + 1] = x
out.extend(b)
return out
def minstd(seed: int, n: int) -> list[int]:
out, x = [], seed
for _ in range(n):
x = x * 48271 % 2147483647
out.append(x)
return out
if __name__ == "__main__":
clrs = [2, 5, 3, 0, 2, 3, 0, 3]
assert counting_sort(clrs) == [0, 0, 2, 2, 3, 3, 3, 5]
assert counting_sort_indices(clrs, 5) == [3, 6, 0, 4, 2, 5, 7, 1]
assert radix_sort_lsd([170, 45, 75, 90, 802, 24, 2, 66]) == [2, 24, 45, 66, 75, 90, 170, 802]
r = minstd(42, 2000)
signed = [x % 2_000_001 - 1_000_000 for x in r] + [-2**31, 2**31 - 1, 0, -1, 1]
assert radix_sort_lsd(signed) == sorted(signed)
small = [x % 201 - 100 for x in r]
assert counting_sort(small) == sorted(small)
reals = [x / 2147483647 for x in r]
assert bucket_sort(reals) == sorted(reals)
keys = [x % 10 for x in minstd(7, 2000)]
p = counting_sort_indices(keys, 9)
assert sorted(p) == list(range(2000))
for u, v in zip(p, p[1:]):
assert keys[u] < keys[v] or (keys[u] == keys[v] and u < v) # sorted and stable
assert counting_sort([]) == [] and radix_sort_lsd([]) == [] and bucket_sort([]) == []
print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NonComparisonSorts {
static int[] countingSort(int[] a) {
if (a.length == 0) return new int[0];
int lo = Arrays.stream(a).min().getAsInt(), hi = Arrays.stream(a).max().getAsInt();
int[] count = new int[hi - lo + 1];
for (int x : a) count[x - lo]++;
for (int v = 1; v < count.length; v++) count[v] += count[v - 1];
int[] out = new int[a.length];
for (int j = a.length - 1; j >= 0; j--) out[--count[a[j] - lo]] = a[j];
return out;
}
static int[] countingSortIndices(int[] keys, int k) {
int[] start = new int[k + 1];
for (int x : keys) start[x]++;
int total = 0;
for (int v = 0; v <= k; v++) { int c = start[v]; start[v] = total; total += c; }
int[] p = new int[keys.length];
for (int j = 0; j < keys.length; j++) p[start[keys[j]]++] = j;
return p;
}
/** 32-bit signed ints: 4 stable passes on bytes of (x ^ MIN_VALUE). */
static int[] radixSortLsd(int[] a) {
int[] src = a.clone(), dst = new int[a.length];
for (int shift = 0; shift < 32; shift += 8) {
int[] count = new int[257];
for (int x : src) count[(((x ^ Integer.MIN_VALUE) >>> shift) & 255) + 1]++;
for (int d = 0; d < 256; d++) count[d + 1] += count[d];
for (int x : src) dst[count[((x ^ Integer.MIN_VALUE) >>> shift) & 255]++] = x;
int[] t = src; src = dst; dst = t;
}
return src;
}
static double[] bucketSort(double[] a) {
int n = a.length;
List<List<Double>> buckets = new ArrayList<>();
for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
for (double x : a) buckets.get((int) (x * n)).add(x);
double[] out = new double[n];
int pos = 0;
for (List<Double> b : buckets) {
for (int i = 1; i < b.size(); i++) {
double x = b.get(i);
int j = i - 1;
while (j >= 0 && b.get(j) > x) { b.set(j + 1, b.get(j)); j--; }
b.set(j + 1, x);
}
for (double x : b) out[pos++] = x;
}
return out;
}
static long[] minstd(long seed, int n) {
long[] out = new long[n];
long x = seed;
for (int k = 0; k < n; k++) { x = x * 48271 % 2147483647L; out[k] = x; }
return out;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[] clrs = {2, 5, 3, 0, 2, 3, 0, 3};
check(Arrays.equals(countingSort(clrs), new int[] {0, 0, 2, 2, 3, 3, 3, 5}), "counting");
check(Arrays.equals(countingSortIndices(clrs, 5), new int[] {3, 6, 0, 4, 2, 5, 7, 1}), "indices");
check(Arrays.equals(radixSortLsd(new int[] {170, 45, 75, 90, 802, 24, 2, 66}),
new int[] {2, 24, 45, 66, 75, 90, 170, 802}), "lsd example");
long[] r = minstd(42, 2000);
int[] signed = new int[2005], small = new int[2000];
double[] reals = new double[2000];
for (int k = 0; k < 2000; k++) {
signed[k] = (int) (r[k] % 2_000_001 - 1_000_000);
small[k] = (int) (r[k] % 201 - 100);
reals[k] = r[k] / 2147483647.0;
}
int[] extremes = {Integer.MIN_VALUE, Integer.MAX_VALUE, 0, -1, 1};
System.arraycopy(extremes, 0, signed, 2000, 5);
int[] e1 = signed.clone(); Arrays.sort(e1);
check(Arrays.equals(radixSortLsd(signed), e1), "radix");
int[] e2 = small.clone(); Arrays.sort(e2);
check(Arrays.equals(countingSort(small), e2), "counting small");
double[] e3 = reals.clone(); Arrays.sort(e3);
check(Arrays.equals(bucketSort(reals), e3), "bucket");
long[] r7 = minstd(7, 2000);
int[] keys = new int[2000];
for (int k = 0; k < 2000; k++) keys[k] = (int) (r7[k] % 10);
int[] p = countingSortIndices(keys, 9);
for (int k = 0; k + 1 < p.length; k++) {
int u = p[k], v = p[k + 1];
check(keys[u] < keys[v] || (keys[u] == keys[v] && u < v), "stable");
}
check(countingSort(new int[0]).length == 0 && radixSortLsd(new int[0]).length == 0, "empty");
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>
std::vector<int> countingSort(const std::vector<int>& a) {
if (a.empty()) return {};
auto [mn, mx] = std::minmax_element(a.begin(), a.end());
int lo = *mn, hi = *mx;
std::vector<int> count(static_cast<std::size_t>(hi - lo) + 1, 0);
for (int x : a) ++count[x - lo];
for (std::size_t v = 1; v < count.size(); ++v) count[v] += count[v - 1];
std::vector<int> out(a.size());
for (std::size_t j = a.size(); j-- > 0;) out[--count[a[j] - lo]] = a[j];
return out;
}
std::vector<int> countingSortIndices(const std::vector<int>& keys, int k) {
std::vector<int> start(k + 1, 0);
for (int x : keys) ++start[x];
int total = 0;
for (int v = 0; v <= k; ++v) { int c = start[v]; start[v] = total; total += c; }
std::vector<int> p(keys.size());
for (int j = 0; j < static_cast<int>(keys.size()); ++j) p[start[keys[j]]++] = j;
return p;
}
// 32-bit signed ints: 4 stable passes on bytes of (x with the sign bit flipped).
std::vector<int> radixSortLsd(const std::vector<int>& a) {
std::vector<std::uint32_t> src(a.size()), dst(a.size());
for (std::size_t i = 0; i < a.size(); ++i) src[i] = static_cast<std::uint32_t>(a[i]) ^ 0x80000000u;
for (int shift = 0; shift < 32; shift += 8) {
std::vector<std::size_t> count(257, 0);
for (auto u : src) ++count[((u >> shift) & 255u) + 1];
for (int d = 0; d < 256; ++d) count[d + 1] += count[d];
for (auto u : src) dst[count[(u >> shift) & 255u]++] = u;
std::swap(src, dst);
}
std::vector<int> out(a.size());
for (std::size_t i = 0; i < a.size(); ++i) out[i] = static_cast<int>(src[i] ^ 0x80000000u);
return out;
}
std::vector<double> bucketSort(const std::vector<double>& a) {
std::size_t n = a.size();
std::vector<std::vector<double>> buckets(n);
for (double x : a) buckets[static_cast<std::size_t>(x * static_cast<double>(n))].push_back(x);
std::vector<double> out;
out.reserve(n);
for (auto& b : buckets) {
for (std::size_t i = 1; i < b.size(); ++i) {
double x = b[i];
std::size_t j = i;
while (j > 0 && b[j - 1] > x) { b[j] = b[j - 1]; --j; }
b[j] = x;
}
out.insert(out.end(), b.begin(), b.end());
}
return out;
}
std::vector<std::int64_t> minstd(std::int64_t seed, int n) {
std::vector<std::int64_t> out;
std::int64_t x = seed;
for (int k = 0; k < n; ++k) { x = x * 48271 % 2147483647LL; out.push_back(x); }
return out;
}
template <class T>
std::vector<T> sortedCopy(std::vector<T> v) { std::sort(v.begin(), v.end()); return v; }
int main() {
std::vector<int> clrs{2, 5, 3, 0, 2, 3, 0, 3};
assert((countingSort(clrs) == std::vector<int>{0, 0, 2, 2, 3, 3, 3, 5}));
assert((countingSortIndices(clrs, 5) == std::vector<int>{3, 6, 0, 4, 2, 5, 7, 1}));
assert((radixSortLsd({170, 45, 75, 90, 802, 24, 2, 66}) == std::vector<int>{2, 24, 45, 66, 75, 90, 170, 802}));
auto r = minstd(42, 2000);
std::vector<int> sgn, small;
std::vector<double> reals;
for (auto x : r) {
sgn.push_back(static_cast<int>(x % 2000001 - 1000000));
small.push_back(static_cast<int>(x % 201 - 100));
reals.push_back(static_cast<double>(x) / 2147483647.0);
}
for (int e : {std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 0, -1, 1}) sgn.push_back(e);
assert(radixSortLsd(sgn) == sortedCopy(sgn));
assert(countingSort(small) == sortedCopy(small));
assert(bucketSort(reals) == sortedCopy(reals));
std::vector<int> keys;
for (auto x : minstd(7, 2000)) keys.push_back(static_cast<int>(x % 10));
auto p = countingSortIndices(keys, 9);
for (std::size_t k = 0; k + 1 < p.size(); ++k) {
int u = p[k], v = p[k + 1];
assert(keys[u] < keys[v] || (keys[u] == keys[v] && u < v));
}
assert(countingSort({}).empty() && radixSortLsd({}).empty() && bucketSort({}).empty());
std::cout << "ok\n";
}
function countingSort(a: number[]): number[] {
if (a.length === 0) return [];
let lo = a[0], hi = a[0];
for (const x of a) { if (x < lo) lo = x; if (x > hi) hi = x; }
const count = new Array<number>(hi - lo + 1).fill(0);
for (const x of a) count[x - lo]++;
for (let v = 1; v < count.length; v++) count[v] += count[v - 1];
const out = new Array<number>(a.length);
for (let j = a.length - 1; j >= 0; j--) out[--count[a[j] - lo]] = a[j];
return out;
}
function countingSortIndices(keys: number[], k: number): number[] {
const start = new Array<number>(k + 1).fill(0);
for (const x of keys) start[x]++;
let total = 0;
for (let v = 0; v <= k; v++) { const c = start[v]; start[v] = total; total += c; }
const p = new Array<number>(keys.length);
keys.forEach((x, j) => { p[start[x]++] = j; });
return p;
}
/** 32-bit signed ints: 4 stable passes on bytes of (x ^ 0x80000000) >>> 0. */
function radixSortLsd(a: number[]): number[] {
let src = a.slice();
let dst = new Array<number>(a.length);
const digit = (x: number, shift: number) => (((x ^ 0x80000000) >>> 0) >>> shift) & 255;
for (let shift = 0; shift < 32; shift += 8) {
const count = new Array<number>(257).fill(0);
for (const x of src) count[digit(x, shift) + 1]++;
for (let d = 0; d < 256; d++) count[d + 1] += count[d];
for (const x of src) dst[count[digit(x, shift)]++] = x;
[src, dst] = [dst, src];
}
return src;
}
function bucketSort(a: number[]): number[] {
const n = a.length;
const buckets: number[][] = Array.from({ length: n }, () => []);
for (const x of a) buckets[Math.floor(x * n)].push(x);
const out: number[] = [];
for (const b of buckets) {
for (let i = 1; i < b.length; i++) {
const x = b[i];
let j = i - 1;
while (j >= 0 && b[j] > x) { b[j + 1] = b[j]; j--; }
b[j + 1] = x;
}
out.push(...b);
}
return out;
}
function minstd(seed: number, n: number): number[] {
const out: number[] = [];
let x = seed;
for (let k = 0; k < n; k++) { x = (x * 48271) % 2147483647; out.push(x); }
return out;
}
function check(ok: boolean, msg: string): void {
if (!ok) throw new Error("check failed: " + msg);
}
const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, k) => v === y[k]);
const asc = (x: number[]) => [...x].sort((p, q) => p - q);
const clrs = [2, 5, 3, 0, 2, 3, 0, 3];
check(same(countingSort(clrs), [0, 0, 2, 2, 3, 3, 3, 5]), "counting");
check(same(countingSortIndices(clrs, 5), [3, 6, 0, 4, 2, 5, 7, 1]), "indices");
check(same(radixSortLsd([170, 45, 75, 90, 802, 24, 2, 66]), [2, 24, 45, 66, 75, 90, 170, 802]), "lsd example");
const r = minstd(42, 2000);
const signed = r.map((x) => (x % 2000001) - 1000000).concat([-(2 ** 31), 2 ** 31 - 1, 0, -1, 1]);
check(same(radixSortLsd(signed), asc(signed)), "radix");
const small = r.map((x) => (x % 201) - 100);
check(same(countingSort(small), asc(small)), "counting small");
const reals = r.map((x) => x / 2147483647);
check(same(bucketSort(reals), asc(reals)), "bucket");
const keys = minstd(7, 2000).map((x) => x % 10);
const p = countingSortIndices(keys, 9);
for (let k = 0; k + 1 < p.length; k++) {
const u = p[k], v = p[k + 1];
check(keys[u] < keys[v] || (keys[u] === keys[v] && u < v), "stable");
}
check(countingSort([]).length === 0 && radixSortLsd([]).length === 0 && bucketSort([]).length === 0, "empty");
console.log("ok");
Variant: MSD radix sort for strings
Recursive MSD on characters, with "end of string" as the smallest digit (bucket 0) and an insertion-sort cutoff for small groups. It reproduces the diagram above.
CUTOFF = 8
def msd_sort(strings: list[str]) -> list[str]:
a = list(strings)
aux = [""] * len(a)
def char_at(s: str, d: int) -> int:
return ord(s[d]) + 1 if d < len(s) else 0 # 0 = end of string
def sort(lo: int, hi: int, d: int) -> None: # sorts a[lo:hi] on characters d..
if hi - lo <= CUTOFF:
for i in range(lo + 1, hi): # insertion sort on suffixes from d
x, j = a[i], i - 1
while j >= lo and a[j][d:] > x[d:]:
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
return
R = 257 # digits 0..256: end-of-string + Latin-1
count = [0] * (R + 1)
for s in a[lo:hi]:
count[char_at(s, d) + 1] += 1
for r in range(R):
count[r + 1] += count[r]
starts = count[:] # starts[r] = first slot of bucket r
for s in a[lo:hi]:
c = char_at(s, d)
aux[count[c]] = s
count[c] += 1
a[lo:hi] = aux[: hi - lo]
for r in range(1, R): # bucket 0 (ended strings) is done
if starts[r + 1] - starts[r] > 1:
sort(lo + starts[r], lo + starts[r + 1], d + 1)
sort(0, len(a), 0)
return a
words = ["sea", "she", "sell", "by", "the", "shell", "shore"]
assert msd_sort(words) == ["by", "sea", "sell", "she", "shell", "shore", "the"]
import random
rng = random.Random(3)
for _ in range(200):
ws = ["".join(rng.choice("abc") for _ in range(rng.randint(0, 6))) for _ in range(rng.randint(0, 40))]
assert msd_sort(ws) == sorted(ws)
print("ok")
Variant: verify the lower-bound table
The numbers in the decision-tree table come from this script; it also checks Stirling's three-term approximation and the ratio at large via lgamma.
import math
for n in (3, 4, 5, 6, 8, 10, 12, 16, 20):
lg = math.log2(math.factorial(n))
stirling = n * math.log2(n) - n * math.log2(math.e) + 0.5 * math.log2(2 * math.pi * n)
assert abs(lg - stirling) < 0.04
print(n, math.factorial(n), round(lg, 2), math.ceil(lg), round(stirling, 2))
assert math.ceil(math.log2(math.factorial(12))) == 29 # yet 30 comparisons are necessary (Wells 1965)
lg_million = math.lgamma(10**6 + 1) / math.log(2)
assert abs(lg_million / (10**6 * math.log2(10**6)) - 0.9276) < 1e-3
Real-world uses
- GPU sorting. NVIDIA's CUB library provides
cub::DeviceRadixSort, and Thrust'sthrust::sortdispatches to a radix sort for primitive keys with the default ordering. Radix sort suits GPUs because each pass is a histogram (parallel counting) plus a prefix sum plus a scatter, all of which parallelise across thousands of threads with no data-dependent branching. The "Onesweep" algorithm (Adinets and Merrill, 2022, arXiv:2206.01784) cuts the global-memory traffic of each digit pass by computing the cross-block prefix sum in a single pass with decoupled look-back. GPU radix sort is also the engine behind depth sorting in rendering and particle systems. - Suffix arrays. The suffix array of a text — the sorted order of all its suffixes — underlies full-text indexes, the Burrows–Wheeler transform in
bzip2, and genome aligners. The classic prefix-doubling construction sorts suffixes by their first characters, using pairs of ranks from the previous round as keys, and each round is a two-pass LSD radix sort on integer ranks, per round and total. Kärkkäinen and Sanders's DC3 ("skew") algorithm (ICALP 2003) builds the suffix array in with radix sorts of triples. See String Algorithms. - Databases. DuckDB's 2021 sort redesign encodes all
ORDER BYcolumns into a single binary string per row and sorts those with radix sort; its blog post states that "the encoding is necessary for Radix sort". PostgreSQL takes a related but different route: since 9.5 its sort uses abbreviated keys fortext,varcharandnumeric(release note: "Improve the speed of sorting of varchar, text, and numeric fields via 'abbreviated' keys"), packing a fixed-size, binary-comparable prefix of each key into a machine word so most comparisons are integer comparisons, and falling back to the full comparator only on ties. That is still a comparison sort (quicksort), but it applies exactly the normalized-key idea that makes radix sorting possible. See How Databases Work and Query Planning & Optimization. - Graph construction. Building a compressed sparse row (CSR) adjacency structure from an edge list is a counting sort of edges by source vertex: histogram the out-degrees, prefix-sum them into row offsets, scatter edges. Graph frameworks and sparse-matrix libraries do this on every load (Graphs).
- Libraries. Boost.Sort's
spreadsortis a hybrid radix/comparison sort for integers, floats and strings. Many high-performance integer sort libraries (ska_sort,vqsort's integer paths, and others) use radix passes for large arrays and fall back to comparison sorts for small ones. - Image processing and statistics. Histogram equalisation, percentile computation over 8- or 16-bit pixel values, and median filters over small ranges are counting sorts in disguise.
- Networking and systems. Timer wheels and calendar queues bucket events by expiry time — bucket sort applied to a priority queue — giving insertion for timers in kernels and network stacks (CPU Scheduling). Bucketed hashing structures such as Consistent Hashing rings and Bloom Filters rely on the same "key as address" idea.
Pitfalls & edge cases
- Left-to-right placement with inclusive prefix sums. Reverses every run of equal keys. With inclusive sums, scan right to left; with exclusive sums, scan left to right.
- Using an unstable digit sort inside LSD radix. Produces wrong output, not just a different tie order — the correctness proof needs stability.
- Negative numbers.
count[x]with negativexsilently indexes from the end in Python and is undefined behaviour in C++. Offset by the minimum (counting sort) or flip the sign bit (radix sort). - Signed shifts. In Java,
x >> shifton a negativeintsign-extends; use>>>. In JavaScript, bitwise operators work on signed 32-bit values;>>> 0converts to unsigned. - Floats. Sorting IEEE floats by their raw bits orders negatives backwards. Use the transform: flip all bits for negatives, the sign bit for non-negatives. Decide where NaN and
-0.0go. - Range explosion. Computing
max - min + 1for counting sort on 64-bit keys can overflow or allocate gigabytes. Check the range before choosing counting sort. - Bucket index of exactly 1.0.
floor(1.0 * n) = nis out of bounds; bucket sort requires , or clamp ton - 1. - Non-uniform data in bucket sort. A distribution concentrated in a narrow band degrades to insertion sort. Use sampled splitters or fall back to a comparison sort.
- Strings of different lengths in MSD. Treat "end of string" as a digit smaller than every character, or
"ab"and"abc"collide. - Small inputs. Radix and counting sort have fixed costs (allocating and scanning counters, extra passes). For below a few hundred, insertion sort or the library sort is faster.
Variations
Pigeonhole sort is counting sort that moves the elements themselves into "holes" (lists), then reads them out in order — simplest when keys are the records.
Radix sort with 16-bit or 11-bit digits trades histogram size for passes. Hybrid radix sorts run MSD passes until buckets are small, then switch to insertion sort or LSD.
American flag sort — in-place MSD by cycle-chasing permutations, extra space per level, unstable (McIlroy, Bostic, McIlroy 1993).
Three-way radix quicksort — quicksort on one character at a time, adaptive to shared prefixes, in place (Bentley and Sedgewick 1997). See Quick Sort.
Samplesort / distribution sort — choose bucket splitters from a sorted random sample so buckets are balanced for any distribution; the basis of parallel sorting on clusters and of external distribution sorts.
Flashsort (Neubert, 1998) — bucket sort with a linear interpolation between min and max as the bucket function, plus an in-place permutation; good on uniform-ish data.
Spreadsort (Ross, 2002; Boost.Sort) — a hybrid that uses radix-style bucketing while it helps and comparison sorting when buckets get small, with a worst case of or better.
Integer sorting in theory — deterministic (Han, 2002) and expected (Han and Thorup, 2002) on the word RAM, beyond the scope of this course but proof that the comparison bound is not the end of the story.
Practice ladder
Easy → hard. Descriptions are paraphrased; follow the links for the exact statements.
- Height Checker (LeetCode 1051) — count positions where heights differ from their sorted order; heights are at most 100. Teaches counting sort when the range is tiny.
Hint
Histogram the heights, then walk the histogram and the array together.
- Relative Sort Array (LeetCode 1122) — order
arr1by the order of values inarr2, then the rest ascending; values are at most 1000. Teaches counting sort with a custom key order.
Hint
Count arr1; emit values in arr2 order with their counts; then emit the remaining values in increasing order.
Solution
def relative_sort_array(arr1: list[int], arr2: list[int]) -> list[int]:
count = [0] * 1001
for x in arr1:
count[x] += 1
out = []
for x in arr2:
out.extend([x] * count[x])
count[x] = 0
for v in range(1001):
out.extend([v] * count[v])
return out
assert relative_sort_array([2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], [2, 1, 4, 3, 9, 6]) == [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
assert relative_sort_array([28, 6, 22, 8, 44, 17], [22, 28, 8, 6]) == [22, 28, 8, 6, 17, 44]
print("ok")
with .
- Array Partition (LeetCode 561) — pair up numbers to maximise the sum of pair minimums; values lie in . Teaches counting sort with an offset for negatives.
Hint
The answer is the sum of every other element in sorted order. Counting-sort with offset .
- Sort Colors (LeetCode 75) — sort 0s, 1s and 2s in place. Teaches the two-pass counting solution, and why the one-pass Dutch flag partition in Quick Sort is the follow-up.
Hint
Count the three values, then overwrite the array.
- H-Index (LeetCode 274) — the largest such that papers have at least citations. Teaches counting sort with values capped at , because anything above behaves the same.
Hint
count[min(c, n)] += 1; scan from down, accumulating, and stop when the accumulated count reaches .
Solution
def h_index(citations: list[int]) -> int:
n = len(citations)
count = [0] * (n + 1)
for c in citations:
count[min(c, n)] += 1
papers = 0
for h in range(n, -1, -1):
papers += count[h] # papers with >= h citations
if papers >= h:
return h
return 0
assert h_index([3, 0, 6, 1, 5]) == 3
assert h_index([1, 3, 1]) == 1
assert h_index([0, 0]) == 0
assert h_index([100]) == 1
print("ok")
time and space, independent of citation magnitudes.
- Sort Characters By Frequency (LeetCode 451) — reorder a string by descending character frequency. Teaches bucket sort by count: frequencies are in .
Hint
Count characters, then put each character into bucket freq; walk buckets from down.
- Top K Frequent Elements (LeetCode 347) — the most frequent values, better than . Teaches bucket sort as a linear-time alternative to a heap.
Hint
Buckets indexed by frequency ; collect from the highest bucket until you have values.
Solution
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
freq = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for v, f in freq.items():
buckets[f].append(v)
out: list[int] = []
for f in range(len(nums), 0, -1):
for v in buckets[f]:
out.append(v)
if len(out) == k:
return out
return out
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
print("ok")
time and space.
- Sort Array by Increasing Frequency (LeetCode 1636) — sort by frequency ascending, ties by value descending. Teaches composite keys: sort by the secondary key first, then stably by the primary key (the LSD idea).
Hint
Stable-sort by value descending, then stable-sort by frequency ascending — or encode both into one key.
- Sort an Array (LeetCode 912) — sort integers in without the built-in. Teaches counting sort when the range is moderate, and LSD radix sort with negative numbers.
Hint
The range is values, comparable to : counting sort with an offset is and simplest. Radix sort with a sign-bit flip also works.
- Query Kth Smallest Trimmed Number (LeetCode 2343) — answer queries about the k-th smallest number after keeping only the last
trimdigits. Teaches that LSD radix sort produces every "sorted by last digits" order as an intermediate — exactly the invariant from the correctness proof.
Hint
Run LSD radix sort on the digit strings (with indices) one digit at a time and keep each intermediate order; a query with `trim = t` reads position <span class="math" data-tex="k - 1"></span> of the order after <span class="math" data-tex="t"></span> passes. Stability gives the required tie-break by index.
- Maximum Gap (LeetCode 164) — the largest difference between neighbours in sorted order, in linear time and space. Teaches the pigeonhole argument behind bucket sort.
Hint
With <span class="math" data-tex="n"></span> values between `lo` and `hi`, the maximum gap is at least <span class="math" data-tex="\lceil (hi - lo)/(n - 1) \rceil"></span>. Use buckets of that width: the maximum gap cannot be inside a bucket, so only each bucket's min and max matter.
Solution
```python
def maximum_gap(nums: list[int]) -> int:
n = len(nums)
if n < 2:
return 0
lo, hi = min(nums), max(nums)
if lo == hi:
return 0
width = max(1, (hi - lo) // (n - 1)) # <= the true maximum gap
m = (hi - lo) // width + 1
bmin, bmax = [None] * m, [None] * m
for x in nums:
b = (x - lo) // width
bmin[b] = x if bmin[b] is None else min(bmin[b], x)
bmax[b] = x if bmax[b] is None else max(bmax[b], x)
best, prev = 0, lo
for b in range(m):
if bmin[b] is not None:
best = max(best, bmin[b] - prev) # gap across empty buckets
prev = bmax[b]
return best
import random
rng = random.Random(1)
assert maximum_gap([3, 6, 9, 1]) == 3 and maximum_gap([10]) == 0 and maximum_gap([1, 1, 1]) == 0
for _ in range(500):
xs = [rng.randint(0, 1000) for _ in range(rng.randint(2, 30))]
s = sorted(xs)
assert maximum_gap(xs) == max(b - a for a, b in zip(s, s[1:]))
print("ok")
```
<span class="math" data-tex="O(n)"></span> time and space. Why it works: the <span class="math" data-tex="n - 1"></span> gaps sum to <span class="math" data-tex="hi - lo"></span>, so the largest gap is at least their average <span class="math" data-tex="(hi - lo)/(n - 1) \ge"></span> `width` (for <span class="math" data-tex="hi - lo \ge n - 1"></span>; otherwise `width` is 1 and every bucket holds one distinct value). Two values in the same bucket differ by at most `width - 1`, which is smaller than the maximum gap, so the maximum gap is always between the max of one non-empty bucket and the min of the next.
- Contains Duplicate III (LeetCode 220) — are there two indices within distance
kwhose values differ by at mostt? Teaches buckets of widtht + 1as a hashing trick: a match is in the same or an adjacent bucket.
Hint
Slide a window of `k` elements, storing one value per bucket `x // (t + 1)` (two values in one bucket already answer yes); check buckets `b - 1`, `b`, `b + 1`.
- Suffix Array (Library Checker) — build the suffix array of a string of length up to . Teaches prefix doubling with radix sort on rank pairs, . Hard.
Hint
Round <span class="math" data-tex="k"></span>: each suffix's key is `(rank[i], rank[i + 2^k])` with <span class="math" data-tex="-1"></span> past the end. Sort pairs with two stable counting-sort passes (second component, then first), recompute ranks, stop when all ranks are distinct.
Solution
```python
def suffix_array(s: str) -> list[int]:
n = len(s)
if n == 0:
return []
rank = [ord(c) for c in s]
sa = list(range(n))
k = 1
while True:
m = max(rank) + 2 # ranks shifted by +1 so that -1 -> 0
second = [rank[i + k] + 1 if i + k < n else 0 for i in range(n)]
first = [r + 1 for r in rank]
def counting_pass(order: list[int], key: list[int]) -> list[int]:
cnt = [0] * (m + 1)
for i in order:
cnt[key[i] + 1] += 1
for v in range(m):
cnt[v + 1] += cnt[v]
out = [0] * n
for i in order: # stable, left to right
out[cnt[key[i]]] = i
cnt[key[i]] += 1
return out
sa = counting_pass(counting_pass(list(range(n)), second), first) # LSD on (first, second)
new = [0] * n
for j in range(1, n):
a, b = sa[j - 1], sa[j]
new[b] = new[a] + ((first[a], second[a]) != (first[b], second[b]))
rank = new
if rank[sa[-1]] == n - 1:
return sa
k *= 2
import random
rng = random.Random(4)
assert suffix_array("abracadabra") == [10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]
for _ in range(200):
t = "".join(rng.choice("ab") for _ in range(rng.randint(1, 30)))
assert suffix_array(t) == sorted(range(len(t)), key=lambda i: t[i:])
print("ok")
```
<span class="math" data-tex="O(n \log n)"></span>: at most <span class="math" data-tex="\lceil \log_2 n \rceil"></span> rounds of two <span class="math" data-tex="O(n + m)"></span> counting passes.
Common mistakes & interview follow-ups
"Prove that sorting needs comparisons." Decision tree with at least leaves, height , and or Stirling. State the model explicitly: the bound is for comparison-based algorithms only.
"Then how does radix sort run in linear time?" It is not a comparison sort: it reads digits and uses them as array indices. Its cost is linear only when the number of digits is constant, i.e. keys of bounded width. For distinct keys you need bits, so "linear" quietly assumes is a constant or machine words.
"Is counting sort stable? Why does it matter?" The right-to-left (or exclusive-sum left-to-right) version is. Radix sort is built on it, and sorting records by multiple keys in successive passes relies on it.
"When would you not use radix sort?" Small ; keys without a natural fixed-width encoding; custom comparators; memory too tight for an buffer; data already nearly sorted (Timsort is there).
"Sort a billion 32-bit integers." Radix sort with 8- or 11-bit digits, histograms computed in one pass, or — if the data does not fit in memory — external sort with radix-sorted runs. For integers in a tiny range, a single counting pass.
"Sort floating-point numbers with radix sort." Reinterpret as unsigned bits, flip all bits for negatives and the sign bit for positives, radix-sort, transform back. Mention NaN.
"What's the expected time of bucket sort, and what assumption is it hiding?" if keys are independent and uniform over the range; worst case with insertion sort inside buckets (or with a comparison sort inside).
"Can you sort in if all values are distinct and between 1 and ?" Yes, and in place: place each value at index value - 1 by cycle-chasing swaps. This is the trick behind "find the missing/duplicate number" problems.
Quick quiz
1. What is the minimum number of comparisons that guarantees sorting 5 elements, according to the decision-tree bound? Is it achievable?
Answer
. Yes: merge-insertion (Ford–Johnson) sorts 5 elements in 7 comparisons. (The bound first fails at , where 30 are needed against a bound of 29.)
2. Counting sort scans the input right to left with inclusive prefix sums. What goes wrong if you scan left to right instead, and how do you fix it without changing the scan direction?
Answer
Equal keys come out reversed (the first occurrence takes the last slot), so the sort is no longer stable and LSD radix sort built on it is incorrect. Fix: compute exclusive prefix sums (first slot of each key) and increment after placing.
3. LSD radix sort on 64-bit keys with 16-bit digits: how many passes, how many counters per pass, and roughly what extra memory for keys?
Answer
4 passes, counters per pass (256 KB with 4-byte counters), and an -element buffer: bytes = 800 MB for 8-byte keys.
4. In the bucket-sort analysis, why is and not ?
Answer
Because , and the binomial variance is not zero. The squared term is what insertion sort pays, so the variance matters; it stays bounded, which is why the total is linear.
5. Does the lower bound still hold if the algorithm may compare sums of elements, e.g. "is ?"
Answer
For sorting, yes: in the linear decision tree model (and the algebraic decision tree model of Ben-Or, 1983), sorting and even element distinctness still require operations. The counting argument still needs distinguishable outcomes. What breaks the bound is indexing memory by key bits, which these models do not allow.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 8: §8.1 (decision-tree lower bound), §8.2 (counting sort, the example used here), §8.3 (radix sort, Lemma 8.4 on choosing the radix), §8.4 (bucket sort and its expected-time proof).
- Donald E. Knuth, The Art of Computer Programming, Vol. 3, §5.2 (sorting by distribution, history of card sorting), §5.3.1 (minimum-comparison sorting, merge-insertion, the result).
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §5.1 (string sorts: key-indexed counting, LSD, MSD, three-way radix quicksort).
- Peter M. McIlroy, Keith Bostic and M. Douglas McIlroy, "Engineering Radix Sort", Computing Systems 6(1), 1993 — American flag sort.
- Jon L. Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", SODA 1997.
- Juha Kärkkäinen and Peter Sanders, "Simple Linear Work Suffix Array Construction", ICALP 2003.
- Andy Adinets and Duane Merrill, "Onesweep: A Faster Least Significant Digit Radix Sort for GPUs", 2022, arXiv:2206.01784.
- Yijie Han, "Deterministic Sorting in O(n log log n) Time and Linear Space", STOC 2002; Han and Thorup, "Integer Sorting in O(n sqrt(log log n)) Expected Time and Linear Space", FOCS 2002.
- Michael Ben-Or, "Lower Bounds for Algebraic Computation Trees", STOC 1983.
- DuckDB blog, "Fastest Table Sort in the West – Redesigning DuckDB's Sort", 2021; PostgreSQL 9.5 release notes (abbreviated keys).
- cp-algorithms, Suffix Array — prefix doubling with counting sort.
Lessons: previous — Heap Sort · next — Sorting in the Real World · module — Searching & Sorting · course map.
Related Archon pages: Sorting & Searching (overview) · Prefix Sums · Hash Tables · String Algorithms · Bit Manipulation · Merge Sort · Probability for Engineers.