Counting sort

The problem it solves

Every comparison sort on this site — bubble, insertion, merge, quick, heap — lives under the same ceiling: no algorithm that learns order only by comparing pairs can beat O(n log n) in the worst case. That bound is proved, not conjectured, and it is airtight. Counting sort’s answer is not to argue with the proof but to walk out of the room it applies to. If the things being sorted are integers in a known, modest range, you do not need to ask how two of them compare — you can read each value and use it as an address.

That one move changes the cost model completely. Tally how many of each value exist (one pass), then write the values back in ascending order (one more pass). Time O(n + k), where k is the size of the value range; space O(k) for the tally table. For grades 0–100, bytes 0–255, ages, dice rolls, digits — anywhere k is comparable to n — this is a linear-time sort, and it is not a trick or an approximation. It is also the machine inside radix sort, which is how the idea scales to values too wide for one tally table.

The visualization makes the foreignness visible: play any comparison sort and the counters panel fills with comparisons; play this one and that counter stays at zero forever.

The intuition — and where it breaks down

Imagine sorting a huge pile of exam papers by grade. Nobody lines them up and compares pairs. You make a hundred labelled slots on a table, deal every paper into its slot, then collect the slots in order. Done. Two passes over the papers, no comparisons, and the “sorting” happened as a side effect of addressing — the grade told you where the paper goes.

The analogy also shows exactly where the idea breaks down, in three directions. First, the table must exist: a hundred slots is nothing, but sort ten values scattered across a billion-wide range and you are allocating a billion slots for ten papers — the O(k) term stops being a footnote and becomes the whole bill. Second, the values must be addresses: floats, arbitrary strings, and anything you can only compare have no slot number, and the technique simply does not apply. Third, in the simple histogram form shown here, the papers are interchangeable once counted — if each element carries satellite data (a record, not just a key), writing back “the value, count times” throws the records away, and you need the prefix-sum variant discussed under implementation notes.

Loading…

A walkthrough you can check

Sort [3, 1, 3, 0, 2, 3]. The range is 0..3, so the tally table has four slots.

1. Tally pass: read each element once. count = [1, 1, 1, 3] — one 0, one 1, one 2, three 3s. Six reads, zero comparisons.
2. Write-back: walk values upward. Value 0 has count 1: write one 0 at index 0. Value 1: write 1 at index 1. Value 2: write 2 at index 2. Value 3 has count 3: write 3 into indices 3, 4, 5.
3. Result: [0, 1, 2, 3, 3, 3]. Six writes — one per element, exactly.

Check the claim the prediction prompt makes: the position where the first copy of a value lands is the sum of the counts of all smaller values. The first 3 landed at index 3 because exactly three elements (one 0, one 1, one 2) are smaller. That cumulative handout is the entire correctness argument, and it is worth being able to reproduce cold.

The invariant

Two, one per phase. After the tally pass, count[v] is exactly the number of occurrences of v — trivially true because each element increments exactly one slot, and nothing else touches the table. During write-back, indices 0..i−1 hold the smallest i values in sorted order, permanently — values are emitted in ascending order, so everything already written is ≤ everything still to come, and no later step revisits a written slot. Watch the drawing: sorted bars settle left-to-right in ink and never move again, which is the stronger “final position” invariant that selection sort has and insertion sort lacks — obtained here without a single comparison.

Together the invariants give correctness in two sentences: every element is tallied once, so the multiset of written values equals the input’s; values are written in ascending order, so the output is sorted.

Complexity, derived

Count the work, phase by phase. Finding the range: one pass, O(n). Tally: one pass, one increment each, O(n). Write-back: the outer loop visits k+1 table slots; the inner loop runs once per element ever counted, which is n total across all slots. Sum: O(n + k) time, and O(k) extra space for the table.

Both terms are load-bearing. When k ≤ n — grades, bytes, digits — the whole thing is O(n) and genuinely beats any comparison sort, with tiny constants (array reads, increments, writes; no branching on data). When k ≫ n the k term dominates: sorting 50 values spread over a million-slot range costs a million slot-visits for 50 elements, and quicksort walks away laughing. The honest summary is that counting sort’s complexity is about the range, not the data — which also means it is completely indifferent to input order: sorted, reversed, adversarial, all identical cost. There is no best case and no worst case, only a k.

What people get wrong

• The off-by-one on the table: max − min slots instead of max − min + 1, which silently drops every occurrence of the maximum. The visualization’s tally annotation counts into the last slot precisely so you can watch it being used.
• Forgetting negatives: value-as-index breaks the moment a value is below zero. The fix is mechanical — shift by the minimum, as the displayed code does — but interviews regularly harvest candidates who index arrays with −3.
• Using the histogram form on records: writing back “the value, count times” is only correct when elements are their keys. Sort employees by age this way and you output ages, not employees. Records need the stable prefix-sum variant.
• Claiming it refutes the n log n bound: it does not; it plays a different game. Saying “counting sort breaks the lower bound” in an interview signals a misunderstanding of what the bound is about — say “it steps outside the comparison model” instead.
• Reaching for it with unknown range: if k is unbounded or unknown, the allocation is unbounded or a scan is needed first; either way the decision to use it needs the range in hand.

Implementation notes

The version drawn here is the histogram form: tally, then emit each value count-many times. It is the shortest correct counting sort and the right one for plain integers.

The stable form, required for records and for radix sort, differs in the second phase. Convert the tally to prefix sums, so count[v] becomes the index where value v’s run begins. Then walk the input (not the table) and copy each element to output[count[key(element)]++]. Two consequences: elements carry their satellite data with them, and equal keys keep their input order — stability, which is not optional inside radix sort. Cost is unchanged, but it needs an O(n) output array; the histogram form can write in place.

Practical notes: compute the range in one pass rather than assuming it; shift by min so negatives cost one subtraction instead of a redesign; and if k is large but the values cluster, consider a hash-map tally — you lose the O(n + k) guarantee but stop paying for empty slots. In real standard libraries this algorithm appears mostly in disguise, as the per-digit engine of radix sort and in bucket-sort hybrids.

The follow-up questions

Does this break the O(n log n) lower bound? No. The bound governs sorts whose only information source is pairwise comparisons. Counting sort reads values as addresses, which is only possible for bounded integer keys — a different computational model with different limits. Both statements are true at once: comparison sorts cannot beat n log n, and counting sort runs in n + k.

How do you make it stable? Prefix sums over the tally, then copy input elements in order into output[count[key]++]. The first occurrence of each key claims the first slot of its run, so ties preserve input order. This is the variant radix sort requires, because an unstable digit pass destroys the previous passes’ work.

When does it lose in practice? When k dwarfs n (huge sparse ranges), when keys are not bounded integers (floats, strings), and when memory is tight enough that O(k) hurts. In each case a comparison sort — or radix, for wide-but-fixed integer keys — is the grown-up choice.

Where does it show up in real systems? As radix sort’s inner loop; in histogram-based analytics; in graphics (depth bucketing); and anywhere the data is bytes — network gear sorts by port and priority fields with exactly this table-of-counters shape.