↩ back to Non-Comparison Sorts
Every sort on this site so far — insertion sort,
merge sort, quicksort,
heap sort — decides where an element goes by
comparing it against other elements. That's not a stylistic choice; it's a hard
floor. Any sort that only asks "is A bigger than B?" needs at least Ω(n log n)
comparisons in the worst case, because there are n! possible orderings and each
comparison can only cut the remaining possibilities in half. Counting sort gets around that bound
entirely — not by comparing faster, but by never comparing at all. It counts how
many times each distinct value occurs, then uses those counts to compute exactly where each value
belongs. The catch — and it's a real one, see Pitfalls — is that this only works when the values
are integers drawn from a small, known range.
Enter a comma-separated list of integers (positive, negative, or zero — but keep the spread between the smallest and largest value reasonably small, this demo caps it at 40). Step through three phases: counting each input value into a bucket, turning those counts into a running total ("how many values are ≤ this one"), then placing each input element directly into its final output slot, scanned right-to-left. The bucket row is keyed by actual value, not array index; the current input index and the bucket it's touching are both highlighted.
Three passes, each doing one simple thing. First, counting: walk the input once
and tally how many times each distinct value appears in a bucket array indexed by value. Second,
prefix summing: turn each bucket's raw count into a running total, so
bucket[v] now means "how many input elements are ≤ v", which is exactly
the one-past-the-end position v's elements occupy in the sorted output. Third,
placing: walk the input a second time, and for each element v, look up
bucket[v], decrement it, and use the new value as v's output index — the
decrement both consumes one slot and, if another v shows up earlier in the input, hands
it the slot just before this one. That last detail is why the placement pass runs
right to left: consuming slots back-to-front means two equal values land in output
in the same relative order they had in the input — stable,
same guarantee merge sort makes with its own tie-breaking comparison, just earned here through
arithmetic instead of a comparison at all.
That prefix-sum bucket array is a one-time, fixed computation — fine for a sort that runs once
over the whole input, but no good for a running total that needs to keep changing. A
Fenwick tree keeps the same
"turn counts into running totals" idea, but supports point updates and prefix queries in
O(log n) each, at the cost of a little more bookkeeping per operation.
Supports negative values via an offset (min), so buckets always index from 0. This
is the exact scheme the demo above steps through:
function countingSort(arr) {
if (arr.length === 0) return [];
const min = Math.min(...arr);
const max = Math.max(...arr);
const buckets = new Array(max - min + 1).fill(0);
for (const v of arr) buckets[v - min]++; // count
for (let i = 1; i < buckets.length; i++) {
buckets[i] += buckets[i - 1]; // prefix sum
}
const output = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) { // place, right to left
const v = arr[i];
output[--buckets[v - min]] = v;
}
return output;
}It doesn't sort arbitrary data — it needs small integer keys. The bucket array
has k+1 slots, one per distinct value in [min, max], so the whole trick
depends on k (the value spread) being reasonably close to n (the element
count). Sorting a million 32-bit integers spanning the full int range would allocate
billions of mostly-empty buckets — worse than any comparison sort. This isn't a limitation of this
particular implementation; it's inherent to the technique. The standard fix for wide numeric keys is
radix sort: counting-sort each digit (or
byte) independently, least significant first, so the bucket count per pass stays small (typically
10 or 256) no matter how large the numbers get.
The Ω(n log n) bound isn't violated, it's dodged. That lower bound
is a theorem about comparison sorts specifically — it says nothing about algorithms that
extract more structure from the keys than "which is bigger." Counting sort's O(n+k)
time looks like it beats n log n because it's answering a fundamentally different
question with fundamentally different information available.
Stability depends on scanning the placement pass in the right direction.
Placing left-to-right instead of right-to-left still produces a correctly sorted array —
the counts are the same either way — but two equal values swap their relative order, since the
first one encountered now claims the later slot instead of the earlier one. A sort that
looks perfectly correct on a plain array of numbers can silently be unstable; the bug only shows up
once you sort records by one field and need ties on that field to preserve their original order
(the same class of subtlety merge sort's own stability
discussion raises with its <= versus < choice).
Time: O(n+k) — one pass to count (O(n)), one pass to
prefix-sum the buckets (O(k)), one pass to place (O(n)). No worst-case
input makes this slower, unlike quicksort's adversarial pivots — the runtime only depends on
n and the key range k, never on the input's original order.
Space: O(n+k) — the bucket array (k+1 slots) plus the
output array (n slots), both allocated on top of the input, unlike
heap sort's O(1) in-place swaps. When
k is O(n) or smaller, this beats every comparison sort on the site
outright; when k is much larger than n, it loses badly, which is exactly
what the first Pitfall above is about.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: this is the default once the key range is small, ahead of pigeonhole sort on every axis that matters.