What is counting sort?
Counting sort skips comparisons entirely. Walk the array once and count how many times each value appears —
in a count array indexed by value — then rebuild the array in order straight from those counts.
No element is ever compared to another, so a full sort costs O(n + k), where k is the range of
possible values.
- Count array
- An array indexed by value that tallies how many times each value showed up
- Range (k)
- How many distinct values are possible, from the smallest to the largest
- Rebuild
- Reading the counts off in order to write the final, sorted array
Why counting sort at all?
Picture a teacher grading six exam scores from 0 to 3. Instead of comparing scores against each other, they just tally: a mark in the "2" column, a mark in the "1" column, and so on down the stack of papers.
Once every paper has a tally mark, the teacher reads the tally sheet in order — all the 0s, then the 1s, then the 2s, then the 3s — and the scores come out sorted. Not one score was ever compared to another.
Every score increments exactly one bucket. No score is ever compared to another.
What kinds of problems does it solve?
Three common shapes, all built on the same tally-then-read mechanic — only what gets tallied, and what order the buckets are read back in, changes.
Count, then rebuild
Tally every value into its bucket. Then walk the buckets from smallest to largest, writing each value out as many times as its count says — the classic counting sort.
The rebuild pass never looks at the original array again — only the counts.
Rank by frequency
Tally how often each value occurs, then read the buckets back ordered by count instead of by
value — the most frequent value comes out first.
Same tally-then-read mechanic — just ordered by count, not by value.
Spot gaps between buckets
Once values are bucketed in order, the biggest jump between one occupied bucket and the next falls out for free — no need to compare every pair, only neighbors in bucket order.
Walking bucket order finds the widest gap in a single pass.
Two passes
Underneath, it's really only two loops: one pass that counts, and one pass that rebuilds. Neither pass ever compares two elements of the input to each other.
Count pass
Walk the input once. For each value, increment the bucket at that value's index. That's the whole pass — an increment, not a comparison.
count-pass.ts
function countPass(values: number[], range: number): number[] {
const counts = new Array(range).fill(0);
for (const value of values) {
counts[value]++; // no comparisons — just increment the bucket
}
return counts;
}
Rebuild pass
Walk the buckets from smallest value to largest. For each bucket, write its value out as many times as its count says, then move to the next bucket.
rebuild-pass.ts
function rebuildPass(counts: number[]): number[] {
const result: number[] = [];
for (let value = 0; value < counts.length; value++) {
for (let i = 0; i < counts[value]; i++) {
result.push(value); // read the bucket off, in order
}
}
return result;
}
Where it works — and where it breaks
Counting sort leans on one quiet assumption: the range of possible values, k, is small and
known ahead of time. Break that assumption and the count array stops paying for itself.
Works when the range is small and known
Exam scores from 0 to 100 need a count array of 101 buckets, no matter how many students took the test. That's a fixed, tiny cost — and it beats any comparison sort's O(n log n) floor.
Breaks when the range is huge or unbounded
Arbitrary floating-point values, or 32-bit integers spanning billions, would need a count array with billions of buckets — mostly empty. The "extra memory" stops being extra and becomes impossible.