Radix Sort

Radix Sort

Radix sort is like sorting a deck of cards by first sorting by suit, then by rank. Instead of comparing whole numbers, it processes them digit by digit. It's a non-comparison sort that can achieve O(n) time when the number of digits d is small relative to n.

The key insight is that you don't need to compare entire numbers to sort them. By processing one digit at a time (from least significant to most significant), you can use a stable sort like counting sort on each digit position. Each pass is O(n), and you need d passes total.

LSD vs MSD Approach

LSD (Least Significant Digit) radix sort processes digits from right to left — starting with the units place, then tens, then hundreds. This is the simpler approach and works great for fixed-length integers. Each pass uses a stable sort to maintain the order from previous passes.

MSD (Most Significant Digit) radix sort processes from left to right, like how a dictionary sorts words — first by the first letter, then by the second, and so on. MSD is more natural for variable-length strings but requires more complex implementation with recursive bucketing.

function radixSort(arr) {
  const max = Math.max(...arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    countingSortByDigit(arr, exp);
    exp *= 10;
  }
  return arr;
}
function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10).fill(0);
  for (const num of arr) {
    const digit = Math.floor(num / exp) % 10;
    count[digit]++;
  }
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}
console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));

Time Complexity

Time complexity is O(d × (n + b)) where d is the number of digits, n is the number of elements, and b is the base (10 for decimal). When d is constant and b is O(n), this simplifies to O(n) — linear time. That's faster than any comparison sort can achieve.

Space complexity is O(n + b) for the output and count arrays. The trade-off is clear: radix sort trades memory for speed. If you have the space and the data fits the constraints, radix sort is incredibly fast.

When to Use Radix Sort

Radix sort excels when sorting integers, fixed-length strings, or anything that can be broken into digits or bytes. It's commonly used in database systems, file systems, and networking (sorting IP addresses). If you need to sort millions of 32-bit integers, radix sort is hard to beat.

Avoid radix sort when the number of digits is large relative to n — if d approaches log(n), you lose the advantage over comparison sorts. It's also not suitable for floating-point numbers without custom handling, or for data that can't be decomposed into digits.