Counting Sort

Don't compare — tally each value's count, turn the tallies into positions, and place every item directly into its slot. O(n + k).

8 min read Watch it move Build it

Counting sort never compares two values. Instead it tallies how many times each possible value appears, converts those tallies into running positions, and drops every item straight into its final slot. Because it sidesteps comparisons entirely, it beats the O(n log n) comparison lower bound — but only when the values come from a small range k.

Three arrays, three passes

1Count: scan the input and tally occurrences of each value into a count[] table of size k.
2Prefix-sum: turn the counts into running totals, so count[v] becomes the number of items ≤ v — i.e. where v's block ends in the output.
3Place: walk the input right to left, decrement count[v], and write each item to that index in the output.

Why right-to-left matters

Filling the output from the end of the input backward, paired with decrementing the prefix sums, keeps equal values in their original order — counting sort is stable. That stability is exactly what lets radix sort chain it digit by digit.

function countingSort(arr, k) { // values in 0..k-1
  const count = new Array(k).fill(0);
  for (const v of arr) count[v]++;          // tally
  for (let i = 1; i < k; i++) count[i] += count[i - 1]; // prefix sums
  const out = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) { // right to left = stable
    out[--count[arr[i]]] = arr[i];
  }
  return out;
}

The range is the catch

Memory and time grow with k, the size of the value range, not with n. Sorting a handful of numbers up to a billion would need a billion-slot count array — useless. Counting sort shines only when k is comparable to n (small integers, ages, letters).

OperationTimeSpace

All cases · k = size of the value rangeO(n + k)O(n + k)

Check yourself

Counting sort can beat the O(n log n) lower bound for sorting. Why doesn't that contradict the bound?