Counting, Radix & Bucket Sort

The 10-second versionCopy Anchor Link

Every sort so far decides order by comparing two elements, and that costs a hard floor of Ω(n log n) comparisons — you cannot do better while comparison is your only tool. The non-comparison sorts escape the floor by refusing to compare keys at all. Counting sort tallies how many times each key appears and lays them out in order. Radix sort sorts one digit (or byte) at a time, using a stable counting sort per pass. Bucket sort scatters values into ordered buckets, then sorts each bucket. All can beat n log n — but only when the keys have structure: a small range, a fixed width, or a known distribution. Give them hostile keys and they collapse.

Why this existedCopy Anchor Link

The comparison sorts were doing fine until the data got industrial. Sorting millions of records where the key is a small integer — a year, an age, a postal code, a byte — only to spend Ω(n log n) comparisons felt wasteful. The key isn't a mystery object; it's a number, and numbers can be used as positions.

The idea is older than electronic computers. Herman Hollerith, building machines for the 1887 / 1890 United States Census, had operators drop punched cards into physical sorting bins organized by one column at a time — least-significant column first, then the next, and so on. That is radix sort, performed by machine tooling, decades before it had a name.

• 1887 — Hollerith's tabulating and sorting machines process the US Census by repeatedly bucketing cards on one column each pass.
• 1954 — Harold H. Seward, at MIT, formally describes counting sort and the radix (distribution) sorting method in his thesis on data-processing machines — giving the technique its algorithmic footing.
• Today — Radix-based sorting is standard inside databases, GPU sorters, and suffix-array construction, wherever keys are integers.

Why it mattered then: the census was drowning in paper, and column-by-column bucketing made a decades-long manual job finish in months. Why it matters now: when your keys are integers with a bounded width, radix sort routinely runs several times faster than the best comparison sort.

Inside the inventor's headCopy Anchor Link

Stare at the lower bound and it feels like a wall: any comparison sort must make at least log₂(n!) comparisons, which is Ω(n log n). You can't beat it with comparisons.

So the pivot is: stop comparing. A comparison extracts only one bit of order — this is bigger, or not. But if you know the keys are, say, integers in the range 0..255, you can just... count them. Make an array with 256 slots, tally how many of each key you saw, then read the slots out in order. No comparison anywhere, and the work is proportional to n plus the range — linear.

The trap — and it's the one that ruins naive implementations — is stability. When you build the output array from your counts, you decide where each key goes. If you write the output left to right, two elements with the same key come out in reverse order, and radix sort then falls apart, because radix depends on earlier passes' order being preserved. Counting sort has to be stable, and that means one deliberate choice: walk the input backwards when placing into the output.

// count[k] → how many keys are <= k; then walk the input right-to-left so// that equal keys land in their original relative order.function countingSort(a, maxKey) {  const count = new Array(maxKey + 1).fill(0);  for (const x of a) count[x]++;  for (let k = 1; k <= maxKey; k++) count[k] += count[k - 1];    // prefix sums  const out = new Array(a.length);  for (let i = a.length - 1; i >= 0; i--) out[--count[a[i]]] = a[i]; // stable placement  return out;}

The final approachCopy Anchor Link

Counting sortCopy Anchor Link

For keys in 0..k: count occurrences, prefix-sum the counts, then place each element at --count[key], scanning the input backwards. O(n + k) time and space.

Radix sort (LSD, base b)Copy Anchor Link

Sort by the least-significant digit first, then the next, and so on, using a stable counting sort each pass. After d passes every key is sorted, because each pass refines the order the previous pass established.

The invariant: after pass p, the array is sorted by the lowest p digits. A stable pass on digit p + 1 preserves the existing order of equal digit-p+1 keys, so the lowest p+1 digits end up sorted. After d passes, all d digits are sorted — which is the whole number.

Bucket sortCopy Anchor Link

If keys are spread roughly uniformly over some range, divide that range into n buckets, drop each value into its bucket, sort each bucket (insertion sort is fine — they're tiny), then concatenate. Average O(n); worst O(n²) if everything lands in one bucket.

A worked trace: LSD radix (base 10)Copy Anchor Link

Sorting [170, 45, 75, 90, 802, 24, 2, 66]:

The last row is fully sorted. The magic is that pass 3 never has to look at the lower digits — the tens and ones passes already ordered them, and stability kept that order intact inside each hundreds group.

It in codeCopy Anchor Link

// One stable counting-sort pass over a single byte of each key.function countingPass(a, shift) {  const count = new Array(256).fill(0);  for (const x of a) count[(x >>> shift) & 0xff]++;  for (let k = 1; k < 256; k++) count[k] += count[k - 1];  const out = new Array(a.length);  for (let i = a.length - 1; i >= 0; i--)    out[--count[(a[i] >>> shift) & 0xff]] = a[i];  return out;}function radixSort(a) {  for (let shift = 0; shift < 32; shift += 8)   // four byte-wide passes    a = countingPass(a, shift);  return a;}

ComplexityCopy Anchor Link

Here k is the key range, d the number of digits, and b the base. The lesson is the trade: these sorts buy their speed by assuming structure in the keys. When the assumption holds, they crush the comparison sorts. When it doesn't — keys spread over 2⁶⁴, or all landed in one bucket — they're slower than simply merging.

Where you meet it todayCopy Anchor Link

• Databases. Column stores and index builders radix-sort integer and date columns — an INT or DATE key is exactly the fixed-width integer these algorithms are built for.
• GPUs. Radix sort parallelizes beautifully (one pass per byte, counts computed in parallel), so it's the standard large-array sort on graphics hardware.
• Suffix arrays and strings. Building a suffix array by prefix doubling uses radix-style counting sorts on ranks each round — the backbone of many string-indexing libraries.
• Any "sort by a small integer key" job. Ages, years, ASCII bytes, or small IDs: when the range is tiny, counting sort is a one-pass win.

// Count occurrences of each byte value in a buffer — counting sort's first half.const hist = new Uint32Array(256);for (const b of data) hist[b]++;

RecapCopy Anchor Link

• Comparison sorts obey a hard floor of Ω(n log n); the non-comparison sorts dodge it by treating keys as indices, not as puzzle pieces to compare.
• Counting sort is O(n + k) and only works when the key range k is small; it must be stable to serve as a radix pass.
• Radix sort runs a stable pass per digit, least-significant first, for O(d·(n + b)) — and it dies without stability.
• Bucket sort is O(n) average but O(n²) worst when the distribution is bad.
• The trade is universal: speed bought by assuming key structure — great when it holds, useless when it doesn't.

Next up: Two Pointers — back to clever index arithmetic, this time to scan in pairs instead of sorting.