Sorting without comparisons
Beat the n log n bound when you know the key range: counting sort, bucket sort and radix sort, with the arithmetic that says which one is worth it.
"You cannot sort faster than O(n log n)" is a statement about comparison sorts, and it is often repeated without the qualifier. The proof is a counting argument: a sort that only ever asks "is a before b" is a binary decision tree, a tree of height h has at most 2ʰ leaves, and the n! possible input orderings each need their own leaf. So h ≥ log₂(n!) ≈ n log₂ n − 1.44n. At n = 10⁶ that is a floor of roughly 1.9 × 10⁷ comparisons, and no comparison sort escapes it.
Stop comparing elements to each other and the argument says nothing at all. If you know the keys are integers in a small range, you can use each key as an array index instead, and index arithmetic is not a comparison.
Counting sort
Count how many of each key there are, turn the counts into starting positions, then place each element where its count says it goes.
def counting_sort(a, key, k): # keys are integers in 0 .. k-1
count = [0] * k
for v in a:
count[key(v)] += 1
total = 0
for d in range(k): # counts -> start index of each key
count[d], total = total, total + count[d]
out = [None] * len(a)
for v in a: # input order in, so the result is stable
out[count[key(v)]] = v
count[key(v)] += 1
return out
Three passes over n and one over k: O(n + k) time, O(n + k) space. It is stable because the placement loop walks the input in order and each key's cursor only moves forward — a property radix sort depends on entirely, and the same stability guarantee that makes multi-pass key sorting legal.
If you only need the sorted values and not the records attached to them, the
whole thing collapses to counting and re-emitting: count, then for each key in
order append it count[d] times.
When k is worth it
The comparison is n + k array operations against roughly n log₂ n
comparisons. Both matter, but memory usually decides first.
| n | k | Counting sort | Comparison sort | Count array |
|---|---|---|---|---|
| 10⁶ | 100 | ≈ 10⁶ steps | ≈ 2 × 10⁷ comparisons | 100 entries |
| 10⁶ | 10⁴ | ≈ 10⁶ steps | ≈ 2 × 10⁷ comparisons | 40 KB in C |
| 10⁶ | 10⁶ | ≈ 2 × 10⁶ steps | ≈ 2 × 10⁷ comparisons | 4 MB in C |
| 10⁶ | 10⁹ | ≈ 10⁹ steps | ≈ 2 × 10⁷ comparisons | 4 GB in C |
At k = 100 counting sort does twenty times fewer operations, and each one is an array increment rather than an interpreted comparison, so the real gap is wider than twenty. At k = 10⁹ it is absurd twice over: the count array does not fit, and the emit loop walks a billion buckets to find a million elements — fifty times slower than sorting.
The rule that survives contact with real inputs: counting sort when k is comparable to n or smaller. Ages 0–120, characters a–z, scores 0–100, a status enum, a day of the year. When k is a user-supplied 64-bit integer, it is the wrong tool and no amount of arithmetic rescues it.
Bucket sort, and the assumption it rests on
Bucket sort is counting sort for values that are not integers. Split the range
into n buckets, drop each value into
min(n - 1, int(n * (v - lo) / (hi - lo))), sort each bucket, concatenate.
The min is not defensive padding. For v == hi the division is exactly 1 and
the expression evaluates to n — with n = 5, lo = 0, hi = 10, the value 10
indexes bucket 5 of buckets 0…4, so without the clamp the snippet crashes on the
maximum element of every input. Handle hi == lo separately: the division is by
zero, and an input whose values are all equal is already sorted.
Under a uniform distribution each bucket holds about one element, so the per-bucket sorts cost O(1) each in expectation and the total is O(n) expected. Under any other distribution that argument evaporates: skewed input piles into a few buckets, and if you sort buckets with insertion sort the worst case is O(n²).
The distribution is not a footnote, it is an input to the algorithm. Say "this is O(n) if the keys are roughly uniform on a known range", or do not claim O(n).
Radix sort is repeated stable counting sort
You cannot counting-sort 32-bit integers directly — k = 2³² ≈ 4.3 × 10⁹. You can sort them one digit at a time in a small base, least significant digit first, with a stable counting sort per pass.
def radix_sort(a, base=256, passes=4):
for p in range(passes):
a = counting_sort(a, key=lambda v: (v // base ** p) % base, k=base)
return a
(v // base ** p) % base is the whole digit arithmetic: divide away the digits
below position p, then take the remainder to keep only digit p. With
base = 256 and 32-bit values, four passes cover every bit, because
256⁴ = 2³² — exactly the number of values there are.
Cost is O(d(n + b)) for d passes in base b. At n = 10⁶ and b = 256:
4 × (10⁶ + 256) ≈ 4 × 10⁶ operations, against 2 × 10⁷ comparisons for a
comparison sort — five times less work. Widen to base = 65,536 and d drops to
2: 2 × (10⁶ + 65,536) ≈ 2.1 × 10⁶ operations, at the price of a 65,536-entry
count array per pass. The trade is always the same one: fewer passes, bigger
buckets.
Every pass must be stable, or the previous passes are erased. Sorting
[12, 15] by the ones digit gives [12, 15]. The tens pass sees two elements
with the same digit, 1 and 1; a stable sort keeps them as [12, 15], an
unstable one is free to return [15, 12] and the ones-digit work is gone. This
is the reason the counting sort above walks the input forward and appends —
change that loop to iterate in reverse without also reversing the cursor logic
and radix quietly stops working.
Two practical limits. Negative numbers need a bias (subtract the minimum first, add it back after), and floats need a bit-level reinterpretation that is almost never worth writing under time pressure.
In an interview
Nobody asks you to implement radix sort. They ask whether you can beat n log n, and the answer they want is the condition, not the algorithm: "yes, if the keys are integers in a bounded range — then it is counting sort in O(n + k)."
Where it actually shows up is as a step inside a larger solution: bucketing frequencies to get the top k in O(n) instead of O(n log n), sorting characters by count, ordering events by a bounded timestamp the way a difference array does. Recognising that a sub-step has a tiny key range is worth more marks than reciting the passes.
The mistake that loses points: saying "counting sort, so O(n)" and dropping the k. It is O(n + k), the interviewer will ask what k is, and at n = 10⁶ with keys running to 10⁹ the answer you just gave was wrong by a factor of a thousand. For unbounded 64-bit keys, k ≈ 1.8 × 10¹⁹ against n = 10⁶: wrong by thirteen orders of magnitude.
Check yourself
n = 10⁶ integers, keys in 0 … 10⁴. Counting sort or a library sort, and by how much?
Counting sort: ≈ 10⁶ + 10⁴ ≈ 10⁶ steps against 10⁶ × 20 = 2 × 10⁷ comparisons, so roughly twenty times fewer operations and a 40 KB count array — 10⁴ entries at four bytes. An easy win.
The same n, keys in 0 … 10⁹. What happens if you try?
The count array needs 10⁹ entries — 4 GB at four bytes — and the emit loop walks all 10⁹ buckets for 10⁶ elements. Sort normally, or radix-sort in four passes of base 256 if the constant matters.
10⁶ records keyed by a 32-bit id, 200 MB of memory. Counting sort, radix sort or the library sort — show the count-array arithmetic that decides it.
Counting sort is out before you write a line: k = 2³² ≈ 4.3 × 10⁹ entries at four bytes is 17 GB against 200 MB. Radix sort in base 256 needs a 256-entry count array per pass — 1 KB — plus one output buffer of n records, and costs 4 × (10⁶ + 256) ≈ 4 × 10⁶ steps against 2 × 10⁷ comparisons. Base 65,536 halves the passes for a 256 KB count array. So radix if that five-fold constant is worth owning the code, library sort otherwise; the one answer that is wrong is counting sort.