Sorting by counting
Counting sort orders integers, or items keyed by small integers, without any comparisons. Instead it tallies how many times each value appears, then uses those tallies to place items directly.
The steps
- Find the range of keys and make a tally array with one slot per possible key.
- Sweep the input, incrementing the tally for each key seen.
- Turn the tallies into running prefix sums, so each entry tells you where that key's block ends in the output.
- Sweep the input again, placing each item at the position its prefix sum points to, decrementing as you go.
When it wins
- The key range is small relative to the number of items, so the tally array is modest.
- You need a stable sort, which the prefix sum placement provides when you sweep the right way.
- It is the workhorse inside radix sort, sorting one digit at a time.
When it hurts
- A huge key range, like full width integers, blows up the tally array memory.
- It only applies to keys you can map to small nonnegative indices.
Key idea
Counting sort tallies occurrences and uses prefix sums to place items, sorting small ranged integers stably and without a single comparison.