Don't memorize counting sort — watch it sort without comparing a single pair. When your values are small integers, you do not need to ask “which is bigger?” at all. Just tally how many times each value appears, then walk the tallies from low to high and emit each value that many times. The result falls out sorted — in linear O(n + k) time.
tally · buckets · emit in order · O(n + k)
COUNT ARRAY
One bucket per possible value, holding how many times it appears.
TALLY
Scan the input once, bumping count[value] for each element.
EMIT
Walk buckets low → high, output each value count[v] times.
NO COMPARE
Never asks which is bigger — so it beats the O(n log n) wall.
Top is the input; middle is a bucket for each value 0…5; bottom is the sorted output. Press Step to tally each input into its bucket, then emit the values in order — no comparisons anywhere.
Tally
Phase
0
Comparisons
Sorting by address, not by contest
Comparison sorts like quicksort and merge sort must ask “is a before b?” over and over, and information theory says that costs at least O(n log n). Counting sort sidesteps the whole question. If every value is a small integer, that integer is its address: value 4 goes in bucket 4, no contest needed. Count the buckets, then read them out in order. The only price is a count array the size of the value range.
01
Make the buckets
Allocate a count array with one slot per possible value, 0 through k, all zero.
02
Tally the input
One pass: for each element, increment count[value]. O(n), and not a single comparison.
03
Emit in order
Walk the counts from 0 to k, outputting each value count[v] times. O(k) plus the n outputs.
04
Make it stable
Use a prefix sum of the counts and place from the back of the input, so equal keys keep their order — the key to radix sort.
Time
O(n + k)
Space
O(n + k)
Comparisons
0
Stable
Yes*
The catch is k. When the value range is comparable to n, counting sort is a linear-time marvel; when k dwarfs n (say sorting a handful of 64-bit numbers), the count array is enormous and wasteful — reach for a comparison sort. Chaining stable counting sort one digit at a time gives radix sort, which sorts big numbers and strings in linear time relative to their length.
SOLVE IT YOURSELF
Solve it: counting sort
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement counting_sort(nums) for non-negative integers — no comparisons and no built-in sort. Tally how many times each value appears in a count array, then emit each value that many times in order. O(n + k), where k is the largest value.
HINTS — 4 IDEAS
Find the maximum value; make a count array of that many + 1 slots, all zero.
One pass over the input: count[x] += 1 for each value x.
Walk the count array from 0 upward; append value v exactly count[v] times.
Handle the empty input (return an empty list) so max is never called on nothing.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · How does counting sort place a value?
The value is its own address — it goes straight into count[value], no comparison needed.
2 · What is the time complexity of counting sort?
One pass to tally n elements plus one pass over k+1 buckets to emit — linear in n plus k.
3 · When is counting sort a poor choice?
A huge k means a huge, mostly-empty count array — wasteful. Use a comparison sort when k dwarfs n.
Questions
How does counting sort beat the O(n log n) lower bound?
That bound only applies to sorts that learn order by comparing elements. Counting sort never compares — it uses each value as an index — so the bound simply does not apply. The cost is that it only works on integer-like keys in a bounded range.
What is the difference from bucket sort?
Bucket sort scatters values into a few ranges (buckets) and sorts each bucket, good for uniformly distributed reals. Counting sort has one bucket per exact value and never sorts within a bucket. They share the bucketing idea but suit different data.
Why does radix sort need counting sort to be stable?
Radix sort sorts by the least significant digit first, then the next, and so on. Each pass must preserve the order established by the previous digits, which requires a stable sub-sort — and stable counting sort provides exactly that.
Count, then pour it out in order.
No swaps, no comparisons — just tallies and a walk from low to high. Linear sorting for bounded keys.