Counting Sort

How it works, step by step

1. 1

   Find the biggest value k, and create a counts array with k+1 slots, all zero.

2. 2

   Walk the input once. For each value v, add one to counts[v]. No comparisons - just a lookup.

3. 3

   Now counts[v] says exactly how many times v appears.

4. 4

   Walk the counts array from 0 up to k. Write each value v into the output counts[v] times.

5. 5

   The output is sorted, because you walked the values in order.

6. 6

   Total work: n steps of counting plus k steps of writing - O(n + k).

The code, in JavaScript

function countingSort(arr) {
  if (arr.length === 0) return [];

  const max = Math.max(...arr);
  const counts = new Array(max + 1).fill(0);

  // Phase 1: tally every value.
  for (const value of arr) {
    counts[value]++;
  }

  // Phase 2: rebuild the array from the tallies, in order.
  const out = [];
  for (let v = 0; v <= max; v++) {
    for (let c = 0; c < counts[v]; c++) {
      out.push(v);
    }
  }

  return out;
}

countingSort([3, 1, 2, 1]);        // → [1, 1, 2, 3]

Dry run: sorting [3, 1, 2, 1]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Counting sort does not beat the O(n log n) "law" by magic - that lower bound only applies to sorts that compare. Counting sort uses the values as addresses instead. Different game, different rules.
• Negative values break the naive version: counts[-3] is not an array slot. Shift by the minimum first (index = value - min) and the range becomes min..max.
• The simple rebuild version is fine for plain numbers, but it loses the original objects - you cannot sort records with it. That is what the stable prefix-sum version is for.
• Watch the memory: `new Array(max + 1)` with max = 2³¹ will not end well. Always know your k before choosing counting sort.

Counting Sort vs. its closest relatives