Counting Sort

Counts occurrences of each value, then places them in order. Works best for small integer ranges.

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

28
75
53
89
66
12
80
35
73
73
48
37
74
54
33
Speed5
Size15
TypeScript
function countingSort(arr: number[]): number[] {
  const min = Math.min(...arr), max = Math.max(...arr);
  const range = max - min + 1;
  const count = new Array(range).fill(0);
  for (let x of arr) count[x - min]++;
  for (let i = 1; i < range; i++) count[i] += count[i - 1];
  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }
  return output;
}