Radix Sort

Sort Digit by Digit with a Stable Inner Sort — O(d·(n+b)) Beats n log n When d Is Small

Radix Sort

Radix sort processes integers one digit position at a time using a stable inner sort — bypassing the comparison lower bound to achieve linear time when the number of digits d is small relative to n.

4 min read Level 3/5 #dsa#sorting#radix-sort

What you'll learn

Implement LSD radix sort using counting sort as the stable inner sort
Derive the O(d·(n+b)) complexity and identify when it beats O(n log n)
Explain why the inner sort must be stable for radix sort to be correct

Radix sort sorts integers by processing one digit (or bit group) at a time, from the least significant digit (LSD) to the most significant digit (MSD). At each pass a stable sort orders the array by the current digit position. Because the inner sort is stable, the result after all d passes is a fully sorted array.

Why LSD Works

Start with the ones digit, then the tens digit, then the hundreds digit, and so on. After sorting by the ones digit, equal ones-digit values retain their relative order from the previous pass — which is why stability is mandatory. By the time the last (most significant) digit pass completes, the overall order is correct.

JavaScript Implementation

The inner sort uses counting sort over the digit values 0 – (base - 1).

function countingSortByDigit(arr, base, digitPlace) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(base).fill(0);

  // Count occurrences of each digit at this position
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(arr[i] / digitPlace) % base;
    count[digit]++;
  }

  // Prefix sums
  for (let i = 1; i < base; i++) {
    count[i] += count[i - 1];
  }

  // Build output right-to-left (stability)
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / digitPlace) % base;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }

  return output;
}

function radixSort(arr, base = 10) {
  const max = Math.max(...arr);

  // Process each digit place (1s, 10s, 100s, ...)
  let digitPlace = 1;
  let result = arr.slice();

  while (Math.floor(max / digitPlace) > 0) {
    result = countingSortByDigit(result, base, digitPlace);
    digitPlace *= base;
  }

  return result;
}

console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));
// => [2, 24, 45, 66, 75, 90, 170, 802]

Complexity Analysis

Case	Time	Space	Stable	In-Place
Best	O(d·(n+b))	O(n+b)	Yes	No
Average	O(d·(n+b))	O(n+b)	Yes	No
Worst	O(d·(n+b))	O(n+b)	Yes	No

d = number of digit positions; b = base (10 for decimal, 256 for byte-at-a-time). Each of the d passes runs a counting sort in O(n + b) time.

When Radix Sort Beats O(n log n)

Compare O(d·(n+b)) with O(n log n). For 32-bit integers with b = 256 (byte-at-a-time processing), d = 4. So the cost is 4·(n + 256) ≈ 4n for large n — essentially O(n), which beats n log n once n is large enough.

The break-even point depends on constants. In practice, merge sort or quicksort often wins for n < 100,000 due to lower overhead. For n in the millions and keys that are fixed-width integers or strings, radix sort becomes competitive.

Choosing the Base

A larger base b reduces d (fewer passes) but increases the count array size and branch pressure. A base of 256 (one byte at a time) is a common sweet spot: 32-bit integers need only 4 passes and the count array fits in L1 cache.

Up Next

TimSort, the algorithm V8 uses for Array.prototype.sort, combines merge sort and insertion sort with a clever notion of “runs” to achieve near-linear performance on real-world data.

TimSort →