Radix Sort

How it works, step by step

1. 1

   Find the biggest number - its digit count says how many passes you need.

2. 2

   Pass 1: put every number into one of ten buckets based on its last digit. Keep the order in which numbers arrive in each bucket.

3. 3

   Empty the buckets back into the array in order: bucket 0 first, then bucket 1, up to bucket 9.

4. 4

   Pass 2: same thing, but bucket by the tens digit. Numbers with the same tens digit stay in the order the last pass gave them - that is the stability doing its job.

5. 5

   Repeat for the hundreds digit, thousands digit... one pass per digit.

6. 6

   After the pass on the highest digit, the array is sorted. Total work: digits × (n + 10).

The code, in JavaScript

function radixSort(arr) {
  if (arr.length === 0) return [];
  let a = [...arr];

  const max = Math.max(...a);

  // One pass per digit: 1s, 10s, 100s...
  for (let div = 1; div <= max; div *= 10) {
    const buckets = Array.from({ length: 10 }, () => []);

    for (const value of a) {
      const digit = Math.floor(value / div) % 10;
      buckets[digit].push(value);      // push keeps arrival order → stable
    }

    a = buckets.flat();                // empty buckets 0..9 in order
  }

  return a;
}

radixSort([170, 45, 75, 2]);           // → [2, 45, 75, 170]

Dry run: sorting [170, 45, 75, 2]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Each pass must be stable - that is the entire trick. Use counting sort or ordered buckets per pass; sneak in an unstable pass and the earlier digits' order is destroyed silently.
• Start from the least significant digit (LSD). Going most-significant-first also exists, but then you must sort each bucket recursively - a different, more complex algorithm.
• Negative numbers break the digit math (`-5 % 10` is `-5` in JavaScript). Offset all values to be non-negative first, or split into negative/positive halves.
• The complexity is O(d·(n + b)), not "O(n) always". For 64-bit random numbers d is ~20 decimal digits - measure before assuming radix wins.

Radix Sort vs. its closest relatives