Radix Sort

Sorts numbers digit by digit, from least to most significant, using counting sort as a subroutine.

Best: O(nk) · Avg: O(nk) · Worst: O(nk) · Space: O(n + k)

58
48
49
69
35
59
23
35
44
39
10
22
23
38
58
Speed5
Size15
TypeScript
function radixSort(arr: number[]): number[] {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10)
    countSort(arr, exp);
  return arr;
}
function countSort(arr: number[], exp: number) {
  const output = new Array(arr.length);
  const count = new Array(10).fill(0);
  for (let x of arr) count[Math.floor(x / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
    count[Math.floor(arr[i] / exp) % 10]--;
  }
  for (let i = 0; i < arr.length; i++) arr[i] = output[i];
}