Radix + Counting Visualization for Coding Interviews
Non-comparison sort; O(n·k) bucket passes by digit.
Concept
Radix sort and counting sort sidestep the n log n lower bound of comparison sorts by exploiting structure in the keys themselves. Counting sort runs in O(n + k) where k is the key range; it is blazingly fast when k is small and O(n + k) space is acceptable. Radix sort stacks counting sort across digits of the key, sorting by least significant digit first (LSD) or most significant digit (MSD). LSD radix gives you O(d (n + b)) where d is the number of digits and b is the base — for 32-bit ints in base 256 that is four passes of linear work. These sorts are stable and avoid any element comparisons, which is why they dominate on strings of fixed width, integer IDs, and network packet sorting. The tradeoff is memory for the count buckets and the assumption that keys fit a bounded alphabet.
How it works
Counting sort makes one pass to tally how many times each key value appears, then a prefix-sum pass turns those counts into positions — count[k] becomes the first index where key k should land. A final backwards scan of the input places each element into its slot and decrements the count, preserving stability. The output is built in an auxiliary array and copied back. Radix sort LSD begins with the least significant digit. For base-10 integers it runs counting sort on the ones place, then the tens, then the hundreds, and so on up to the largest magnitude. Because counting sort is stable, elements that tie on the current digit keep their relative order from previous rounds, which means after d passes the array is fully sorted by all digits. MSD radix recurses on each bucket, which fits variable-length strings better. The key engineering choices are the base (higher base means fewer passes but larger count arrays), handling negatives (bias by the minimum, or split sign), and cache behavior — base 256 on bytes is a sweet spot for 32-bit ints on modern CPUs.
Implementation
import java.util.Arrays;
public final class RadixSort {
private RadixSort() {}
public static void radixSort(int[] a) {
if (a.length == 0) return;
int max = a[0];
for (int x : a) if (x > max) max = x;
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(a, exp);
}
}
static void countingSort(int[] a, int exp) {
int n = a.length;
int[] out = new int[n];
int[] count = new int[10];
for (int x : a) count[(x / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int d = (a[i] / exp) % 10;
out[--count[d]] = a[i];
}
System.arraycopy(out, 0, a, 0, n);
}
public static void countingSort(int[] a) {
if (a.length == 0) return;
int lo = a[0], hi = a[0];
for (int x : a) { if (x < lo) lo = x; if (x > hi) hi = x; }
int[] count = new int[hi - lo + 1];
for (int x : a) count[x - lo]++;
int idx = 0;
for (int v = 0; v < count.length; v++)
while (count[v]-- > 0) a[idx++] = v + lo;
}
}
Complexity
- Radix Time:
O(d (n + b)) - Counting Time:
O(n + k) - Space:
O(n + b) - Stable:
Yes
Common pitfalls
- Counting sort blows up when the key range k is close to n^2 — use radix instead.
- Forgetting stability in the inner counting pass breaks multi-digit radix sort.
- Negative integers need bias or sign-bit flipping; naive radix places negatives after positives.
- Allocating a fresh output array per digit pass thrashes GC — reuse a single buffer.
- Base selection matters: base 2 is too many passes, base too large wastes cache.
Key design decisions & trade-offs
- Base (radix) for int sort — Chosen: Base 256 (per byte). Four passes for 32-bit ints, count array fits in L1 cache.
- LSD vs MSD — Chosen: LSD for fixed-width keys. Simpler, in-place-ish, no recursion overhead; MSD wins for variable-length strings.
- Use radix over quicksort — Chosen: Only when keys are bounded integers or short strings. Radix needs O(n) extra memory and breaks down when keys are long or comparison is complex.
Practice problems
Interview follow-ups
- Extend to sort negative numbers by biasing with the minimum.
- Write an MSD radix sort for strings with variable length.
- Benchmark base 10 vs base 256 on 10 million random ints.
- Add a fallback to insertion sort when buckets are tiny.
Why it matters
Radix + Counting is a core part of the Sorting toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".