Sorting II: Counting Sort, Radix Sort, and Bucket Sort — Beating O(n log n)

In plain words — and an analogy

Imagine sorting 1,000 student exam scores, all integers from 0 to 100. You don't need to compare scores against each other at all — just count how many students scored a 0, how many scored a 1, how many a 2, and so on up to 100. Then write out all the 0s, then all the 1s, and so on. Done. No comparisons, no decision tree — you used the values themselves as array indices. That is counting sort: the key insight that breaks the O(n log n) barrier entirely.

Lesson 19 proved comparison sorts can't beat O(n log n). This lesson's algorithms sidestep that proof entirely by *not comparing elements* — instead they use the keys' actual values as array indices or digits. The trade-off: they only work on keys with special structure (bounded integers, fixed-length strings, uniformly distributed values), and they buy their speed with extra memory. When the constraints fit, linear-time sorting is on the table.

Counting sort: index by value

If your keys are integers in a known small range 0…k, you don't need to compare anything — just *count* how many of each value appear, then emit them in order. Count occurrences into an array of size k, then walk that count array to reconstruct the sorted output.

CountingSort(arr, k):          // keys in 0..k
  count  = [0] * (k + 1)
  output = [0] * len(arr)

  // Phase 1: count occurrences
  for x in arr:
    count[x] += 1

  // Phase 2: prefix sums → starting positions
  for i in range(1, k + 1):
    count[i] += count[i - 1]

  // Phase 3: place each element (right to left = stable)
  for x in reversed(arr):
    count[x] -= 1
    output[count[x]] = x

  return output

Worked example: counting sort on exam scores

Input: [4, 2, 2, 8, 3, 3, 1]   (7 elements, range 0..8)

Phase 1 — count occurrences:
  index: 0  1  2  3  4  5  6  7  8
  count: 0  1  2  2  1  0  0  0  1

Phase 2 — prefix sums (starting positions):
  index: 0  1  2  3  4  5  6  7  8
  count: 0  1  3  5  6  6  6  6  7

Phase 3 — place right to left:
  x=1: count[1]=1→0;  output[0] = 1
  x=3: count[3]=5→4;  output[4] = 3
  x=3: count[3]=4→3;  output[3] = 3
  x=8: count[8]=7→6;  output[6] = 8
  x=2: count[2]=3→2;  output[2] = 2
  x=2: count[2]=2→1;  output[1] = 2
  x=4: count[4]=6→5;  output[5] = 4

Output: [1, 2, 2, 3, 3, 4, 8]  ✓  (sorted, stable)

Total: O(n + k) time, O(n + k) space. When k = O(n) — say sorting exam scores 0–100, or ages 0–120 — that's linear, dramatically beating O(n log n). But when k is huge (32-bit integers → k ≈ 4 billion), the count array is impossibly large: counting sort is only viable for *small ranges*. Done with the right-to-left final pass, it's stable, which is exactly what makes it the engine inside radix sort.

Radix sort: one digit at a time

Radix sort handles large integers (or fixed-length strings) by sorting on one digit at a time, using a stable sort (usually counting sort) for each digit. The least-significant-digit (LSD) version sorts by the ones digit, then the tens, then the hundreds — and because each pass is stable, earlier orderings survive as tie-breakers, so after the most significant digit the whole array is sorted.

RadixSortLSD(arr, d, b):   // d digits, base b
  for digit in range(0, d):   // from least to most significant
    // stable-sort arr by digit 'digit' using counting sort
    arr = CountingSortByDigit(arr, digit, b)
  return arr

CountingSortByDigit(arr, digit, b):
  count = [0] * b
  for x in arr:
    count[(x // b**digit) % b] += 1
  // prefix sums, then place right-to-left (same as above)
  ...

Worked example: radix sort traced through all digits

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

Sort by ones digit (d=0):
  170→0  45→5  75→5  90→0  2→2  802→2  24→4  66→6
  After: [170, 90, 2, 802, 24, 45, 75, 66]
  (ties: 170 before 90 — both end in 0, kept in input order)
  (ties: 2 before 802 — both end in 2, kept in input order)
  (ties: 45 before 75 — both end in 5, kept in input order)

Sort by tens digit (d=1) — stable pass:
  170→7  90→9  2→0  802→0  24→2  45→4  75→7  66→6
  After: [2, 802, 24, 45, 66, 170, 75, 90]
  (2 and 802 both have 0 in tens place; 2 came first → stays first)

Sort by hundreds digit (d=2) — stable pass:
  2→0  802→8  24→0  45→0  66→0  170→1  75→0  90→0
  After: [2, 24, 45, 66, 75, 90, 170, 802]  ✓  SORTED!

With d digits and radix (base) b, radix sort is O(d · (n + b)). Treating d and b as constants (fixed-width integers in a fixed base), that's O(n) — linear. The stability of each counting-sort pass is load-bearing: use an unstable sort per digit and radix sort produces garbage.

Bucket sort: scatter, sort, gather

Bucket sort suits keys drawn from a *uniform distribution* over a known range (e.g., random floats in [0, 1)). Divide the range into n buckets, scatter each element into the bucket its value falls in, sort each bucket individually (insertion sort, since buckets are tiny), then concatenate the buckets in order.

BucketSort(arr):
  n = len(arr)
  buckets = [[] for _ in range(n)]

  // Scatter: each element goes to bucket floor(x * n)
  for x in arr:
    buckets[int(x * n)].append(x)

  // Sort each bucket individually (insertion sort is fine)
  for bucket in buckets:
    InsertionSort(bucket)

  // Gather: concatenate all buckets
  return [x for bucket in buckets for x in bucket]

Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12]

With n=8 buckets covering [0, 0.125), [0.125, 0.25), ...

Bucket 0 [0.000-0.125): [0.12]
Bucket 1 [0.125-0.250): [0.17, 0.21]       ← sort these 2
Bucket 2 [0.250-0.375): [0.26]
Bucket 3 [0.375-0.500): [0.39]
Bucket 4 [0.500-0.625): []
Bucket 5 [0.625-0.750): []
Bucket 6 [0.750-0.875): [0.78, 0.72]       ← sort these 2
Bucket 7 [0.875-1.000): [0.94]

Concatenate: [0.12, 0.17, 0.21, 0.26, 0.39, 0.72, 0.78, 0.94] ✓

When the data is genuinely uniform, each bucket holds about one element, so the per-bucket sorting is trivial and the whole thing is O(n) average. But the assumption is fragile: if the data clusters, one bucket could receive everything, degrading to the O(n²) of whatever sorts the buckets. Bucket sort is a strong choice for uniform numeric data and a poor one for skewed data — know your distribution before reaching for it.

The three compared

The headline distinction: these three assume something extra about the keys — a bounded range, a digit structure, a distribution — and exploit it to skip comparisons. Comparison sorts assume nothing and pay O(n log n) for that generality. When your data fits a non-comparison sort's assumptions, it can be several times faster; when it doesn't, it's inapplicable or degrades badly.

Under the hood: why O(n log n) doesn't apply here

The decision-tree lower bound proof from Lesson 19 assumed the algorithm's only way to gain information is from comparing two elements — each comparison gives one bit. Counting sort never compares elements; it uses the values themselves as indices into a table, reading the full value (not just greater/less) in one O(1) step. That's multiple bits of information per step, so the decision-tree model simply doesn't apply. Radix sort similarly reads digit values rather than comparing whole numbers. This is not cleverness that somehow beats the lower bound — it's operating outside its assumptions entirely.

Common pitfalls

• Counting sort on a large key range. k = 4 billion means a 4-billion-slot array. Counting sort is *only* for small ranges; check that k = O(n) before using it.
• Using an unstable per-digit sort in radix sort. Radix sort's correctness *depends* on each digit pass being stable. Break stability and the whole sort breaks.
• Bucket sort on skewed data. Non-uniform data piles into a few buckets and degrades to O(n²). Verify (or ensure) uniformity first.
• Forgetting the memory cost. All three trade space for time — O(n + k) or O(n + b) auxiliary memory. On memory-constrained systems the in-place comparison sorts may still win.
• Reaching for these by default. They're specialists. For arbitrary comparable objects (strings by locale, custom comparators, floats with edge cases), a comparison sort is the correct, safe choice.

When to use vs avoid

• Counting sort: small-range integer keys — ages, scores, byte values, small categorical labels. Also the stable subroutine inside radix sort.
• Radix sort: large fixed-width integers, fixed-length strings/IDs, and as a fast sort for keys that comparison sorts would handle in O(n log n) but radix handles in O(n).
• Bucket sort: floating-point or numeric data known to be uniformly distributed over a range.
• Avoid all three: arbitrary comparable keys, unknown or skewed distributions, huge key ranges, or tight memory — fall back to the O(n log n) comparison sorts.

Practice problems

1. Sort array by parity. Separate even and odd integers, evens first. (A counting-sort-style approach using two buckets [even, odd] works in O(n) time and O(n) space — or in-place with a two-pointer approach.)
2. Maximum gap. Given an unsorted array, find the maximum difference between successive elements in its sorted form, in O(n) time. (Use bucket sort: distribute n elements into n+1 buckets of width (max−min)/n. The maximum gap must span at least one empty bucket, so only compare min/max of adjacent non-empty buckets.)
3. Sort strings of the same length. Given n strings each of exactly d characters, sort them lexicographically in O(d·n) time. (LSD radix sort, treating each character position as a digit with base equal to the alphabet size.)

Key takeaways

• The O(n log n) barrier only binds *comparison* sorts; these three don't compare, so they can be linear.
• Counting sort: O(n + k), stable, for small integer ranges — index directly by value.
• Radix sort: O(d·(n+b)) ≈ O(n) for fixed-width keys, by stably sorting one digit at a time (LSD).
• Bucket sort: O(n) average for uniformly distributed data, but O(n²) if the data clusters.
• These are specialists that trade memory and generality for speed; comparison sorts remain the default for arbitrary keys.

Sorting's biggest payoff is what it enables: searching sorted data in O(log n). Next, binary search and its patterns — deceptively simple, endlessly reusable. Drill non-comparison sorts in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play