jsschools

Radix Sort

Non-comparison sort that processes integer keys digit by digit (from least to most significant) using a stable sort (e.g. counting sort) at each digit position.

Spec ↗

Syntax

radixSort(arr)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes Array of non-negative integers to sort. Returns a new sorted array.

Returns

Array<number> — A new sorted array of non-negative integers.

Examples

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const out = new Array(n);
  const count = new Array(10).fill(0);
  for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = n - 1; i >= 0; i--) {
    const d = Math.floor(arr[i] / exp) % 10;
    out[--count[d]] = arr[i];
  }
  return out;
}

function radixSort(arr) {
  const max = Math.max(...arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    arr = countingSortByDigit(arr, exp);
    exp *= 10;
  }
  return arr;
}

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

// Single-digit numbers
function radixSort(arr) {
  if (!arr.length) return arr;
  const max = Math.max(...arr);
  let exp = 1, a = [...arr];
  while (Math.floor(max / exp) > 0) {
    const count = new Array(10).fill(0);
    const out = new Array(a.length);
    for (const x of a) count[Math.floor(x / exp) % 10]++;
    for (let i = 1; i < 10; i++) count[i] += count[i - 1];
    for (let i = a.length - 1; i >= 0; i--) {
      const d = Math.floor(a[i] / exp) % 10;
      out[--count[d]] = a[i];
    }
    a = out; exp *= 10;
  }
  return a;
}

console.log(radixSort([3, 1, 4, 1, 5, 9, 2, 6]));
Output 
[ 1, 1, 2, 3, 4, 5, 6, 9 ]

Notes

| Case | Time | Space | |---------|-----------|-------| | Best | O(nk) | O(n) | | Average | O(nk) | O(n) | | Worst | O(nk) | O(n) | where k = number of digits in the maximum value. For fixed-width integers (e.g. 32-bit) k is a constant, giving true O(n) behaviour. LSD (least significant digit) radix sort is stable; MSD (most significant digit) can be done in-place but is more complex. Not suitable for floating-point or arbitrary objects without a key extraction function.

See also