Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Look at the ones digit of every number.
  2. Drop each number into the bucket matching that digit.
  3. Collect the buckets back in order, 0 through 9.
  4. Repeat on the tens digit, then the hundreds, and so on.
  5. Because each pass is stable, earlier digit order survives.
  6. After the pass for the largest digit position, the array is sorted.

Key concepts

  • Non-comparative: the comparison counter stays at zero
  • Stability is what makes it correct, not an extra feature
  • Cost scales with digit count k, not with log n
  • Needs O(n) scratch space for the buckets

When to use it

When keys are fixed-width integers and n is large. It beats the O(n log n) comparison bound because it never compares.

Did you know

Radix sort predates computers: Herman Hollerith used it on punched-card machines for the 1890 US census.