↩ 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 [];
let min = arr[0], max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) min = arr[i];
if (arr[i] > max) max = arr[i];
}
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).
The classic Math.min(...arr)/Math.max(...arr) idiom has its
own hidden array-size limit, unrelated to k. Spreading an array into a
function call pushes every element onto the JS engine's call stack as a separate argument. The
reference implementation above used exactly that idiom until this fix — and it threw
RangeError: Maximum call stack size exceeded on any array past roughly 125,000
elements, measured by bisection in Node v20.20.2's default stack size (the exact cutoff is
stack-size- and engine-dependent, not a fixed constant, but the failure mode is real and silent
until it happens). Caught while measuring the crossover below, not before — a genuine bug this
page shipped with, and a pointed one: the whole case for counting sort is handling more
data than a comparison sort can efficiently, yet the buggy version couldn't accept that much data
at all. Fixed by computing min/max with a plain loop instead of spread,
which has no stack depth and no array-size ceiling.
The Complexity section below says this beats every comparison sort "outright" when
k is O(n) or smaller, and "loses badly" once k is "much
larger than n" — true in direction, but with no number behind either half, and this
page's own demo only ever runs 7 elements with k≈n by construction, never
testing the far side of either claim. Measured directly here: this page's own fixed
countingSort above against Quicksort's own reference
implementation, wall-clock, on identical random input (correctness cross-checked against each
other first, 0 mismatches across 200 random trials).
At k = n — the regime "outright" describes — counting sort does win throughout,
but the margin is not fixed: roughly 4× faster at n=1,000, widening to
roughly 5× at n=10,000, then narrowing to roughly 2.2×
at n=100,000 and down to roughly 1.3× at n=1,000,000. "Outright" undersells
how close the race gets at the sizes this site's other sort pages actually benchmark at.
Holding n=100,000 fixed and growing k finds where the win actually stops — and it's
sooner than "much larger than n" suggests. Counting sort is still ahead at k/n=5
(≈1.3×), but Quicksort pulls ahead by k/n=10 (counting sort already
≈1.3× slower), and by k/n=100 counting sort is roughly
12× slower — a real loss, but "much larger" turns out to mean "about an
order of magnitude," not the many-orders-of-magnitude gap the phrase might suggest to a reader
picturing, say, sorting 32-bit integers.
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 a real comparison sort — see
measuring the crossover above for the actual margin and
where it reverses, which turns out to be sooner than "much larger than n" suggests; the underlying
reason k matters at all is the first Pitfall above.
See Choosing a Non-Comparison Sort for how this compares against the site's other eleven 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.