Where it runs
1. The problem
The sorts you have seen so far all compare pairs. They ask whether one number is bigger than another, and the answer decides whether to swap them or move on. Every comparison sort is built on that question, and because of it no comparison sort can do better than about n log n work.
Now a different situation. You have a lot of numbers, but they are all whole numbers from a small range. Ages from 0 to about 120. Star ratings from 1 to 5. Test scores from 0 to 100. When the values lie in a range that small, you can sort without comparing anything.
You have 100,000 survey responses, each with a rating from 1 to 5 stars. You want them ordered from 1 star up to 5 stars. Comparing the responses with each other is wasted work: there are only 5 different values.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedcountingSort([3, 1, 4, 1, 0, 3, 2], 4)Every key is between 0 and 4, so make 5 counters, one per possible key.
One operation is one comparison, one read or one write. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n + k)O(n log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- keys are integers in a small known range
- sort ages, grades, or bounded counts
- need O(n) and comparisons are the bottleneck
- sort by digit or fixed-width key
- n large but the value range is much smaller than n
Looks similar, isn't
- Fast sort (merge / quick)
No comparison sort can beat n log n. Reading the key steps around that limit entirely.
- Hash set / map
A map counts values too, but it keeps no order. Counting sort uses the value as an index.
- Sort with a custom comparator
A comparator describes the order between two items. Counting sort never looks at two items.
- Elementary sorts (selection, bubble, insertion)
Those compare neighbours and cost n squared. Counting sort is linear when the range allows it.
n values with keys under k gives O(n + k). Radix sort costs O(d times n) across d digits.
On LeetCode
Problems where the values are whole numbers from a small range, like heights up to 100 or citations capped at n. Count each value, then write the values out in order, with no comparisons.
Heights run from 1 to 100, so a tally of 101 counters gives the sorted order to compare with.
Values go up to 1000, so count them, write out arr2's values first, then the rest from low to high.
Three possible values, so three counters and one rewrite of the array.
Cap each citation count at n, tally them, and walk the tally down from n.