Counting sort
Counting sort does not sort by comparing values at all. If you know every value is a whole number between, say, 1 and 40, you can simply count how many of each there are, and from the counts work out where each one belongs. For a small range that is about as fast as sorting can be.
Count
Find the smallest and largest value and make one counter for every value in between, all starting at zero. Read the list once from start to end and add one to the counter of every value you see. The counters now form a histogram: how many 1s, how many 2s, and so on. With n values and k counters, this takes n steps.
Add up
The values equal to the smallest value come first, so their run starts at place 1. The next value's run starts right after them, and so on: each run starts after the sum of all the counts before it. These running totals, called prefix sums, turn the histogram into a map of the sorted list. This takes k steps.
Place
Read the list a second time and move every value to the next free place in its run. Because the values are moved in the order they appear, equal values keep their original order: counting sort is stable. Copy the buffer back, and the list is sorted. The app shows each counter going back down as its values are placed.
An example
Take 4, 1, 3, 4, 2, 1, 4. The counters for 1 to 4 end at 2, 1, 1 and 3. Adding up gives the runs: the 1s at places 1 and 2, the 2 at place 3, the 3 at place 4, and the 4s at places 5 to 7. Placing the values in list order gives 1, 1, 2, 3, 4, 4, 4: 7 values counted, 14 moves, 4 counters, and no comparisons.
When to use it
The total work grows with n + k. When k is small compared with n, such as a thousand exam scores from 0 to 100, counting sort is faster than any comparison sort, which needs about n log₂ n comparisons. When the range is wide it is wasteful: a few values spread up to a million need a million counters. Radix sort solves that by running counting sort once per digit, so each pass only needs ten counters. Harold Seward described counting sort, together with radix sort, in 1954.
Explore it
Open the app and press Step. The strip between the list and the buffer row shows one counter per value. Watch the counters fill while the list is read, the runs appear in the buffer when the counts are added up, and the counters go back down as the values are placed. Choose few unique values to see big runs, or type numbers far apart to see how many counters a wide range needs.
Frequently asked questions
What is the time complexity of counting sort?
O(n + k) for n values and k possible values, and O(n + k) extra memory for the counters and the buffer.
Why is counting sort not always the fastest?
Because its cost depends on the range of the values, not only on how many there are. If the range is much larger than the list, most counters stay at zero and the time and memory go to waste.
Can counting sort handle negative numbers?
Yes. Counters run from the smallest value to the largest, so subtract the smallest value to get a counter's index. The app does the same.
Is counting sort stable?
Yes, as long as the values are moved in list order to the next free place in their run. Radix sort depends on that.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try counting sort