Counting sort

Medium TimeO(n + k) SpaceO(k)

Given an array arr of whole numbers, zero or greater, return them in ascending order without comparing any two values against each other. Duplicates appear as many times as they occur. The values have to stay small enough that a counter can be held for every one from 0 up to the largest.

Examples

Example 1

Input
arr = [4, 2, 2, 8, 3, 3, 1]
Output
[1,2,2,3,3,4,8]
Seven values ascending, with both 2s and both 3s kept.

Example 2

Input
arr = [0, 5]
Output
[0,5]
Two values, but six counters: the four between 0 and 5 stay empty.

The Code

function countingSort(arr) {
  const max = Math.max(...arr);
  const counts = new Array(max + 1).fill(0);
  for (const x of arr) counts[x]++;
  const out = [];
  for (let v = 0; v <= max; v++) {
    for (let c = 0; c < counts[v]; c++) out.push(v);
  }
  return out;
}
countingSort([4, 2, 2, 8, 3, 3, 1]);
Done

The first 13 calls, of 31. This one does not fit on a page.

Step through countingSort([4, 2, 2, 8, 3, 3, 1]) call by call

More like this

All sorting examples (8) →