Counting sort, explained

Most sorting algorithms work by comparing two items. Counting sort takes a different route. It counts how many times each value appears, then writes the values back in order using those counts.

It only works when the values are whole numbers in a fairly small range.

How it works

• Find the range of values, from the smallest to the largest.
• Count how many times each value appears.
• Add up the counts so each value knows where its group starts.
• Write the items into their positions, going through the input in order to keep it stable.

A small example

Sort this list:

4 2 2 8 3 3 1

Counts:  1 appears 1x, 2 appears 2x, 3 appears 2x, 4 appears 1x, 8 appears 1x
Result:  1 2 2 3 3 4 8

What to know about its cost

• O(n + k) time, where k is the size of the value range.
• Needs O(k) extra space.
• Stable when the items are placed in input order.

Where it works well

• Very fast when the range is small.
• No comparisons at all.

Where it struggles

• Wasteful when the range is huge compared with the number of items.
• Only works for integers or things that map to small integers.

Try it yourself

Open the Sorting experiment, enter a list with many repeated values such as 4 2 2 8 3 3 1, choose Counting Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment