- Being counted
- Just moved
- In place
Counting sort
Counting sort works when the values are whole numbers in a small range. It keeps one counter for every possible value, counts how often each one appears, and from those counts knows exactly where every value belongs. Watch the counters fill as the list is read, then empty again as each value moves into its run, one move at a time. Press Play to watch the sort, or Step and Back to go one move at a time. Drag the step slider to jump anywhere. The strip between the list and the buffer row holds one counter for each value. The tiles count the values counted, the moves and the counters. Choose how many bars, how they start, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose how many bars and how they start, or type your own whole numbers. Try a list with few unique values.
- Press Play, or use Step and Back to move one value at a time. Drag the step slider to jump anywhere in the sort.
- Watch the counters: they fill up while the list is read, then count down as each value is placed.
How counting sort works
Make a counter for every value from the smallest to the largest. Read the list once and add one to the counter of each value you see. Then add up the counts from the smallest value: a value's run starts right after all the smaller values. Finally go through the list again and move every value to the next free place in its run, and copy the result back.
Fast for a small range
Counting sort reads the list twice and goes through the counters once, so its work grows with n + k: the number of values plus the number of counters. For many values in a small range, such as exam scores from 0 to 100 or ages, that beats any comparison sort. For a wide range it wastes time and memory on counters nobody uses: three values spread from 1 to 1,000,000 would need a million counters. It is also the step radix sort repeats for every digit.
Frequently asked questions
How does counting sort work?
It counts how often each value appears, adds up the counts to find where each value's run starts, and then moves every value straight into the next free place of its run. It never compares two values.
When should you use counting sort?
When the values are whole numbers, or can be turned into them, and the range from smallest to largest is not much larger than the number of values: grades, ages, small codes. Then it takes time proportional to n + k.
Is counting sort stable?
Yes, when the values are moved in list order to the next free place of their run, as here. That is what lets radix sort use it for each digit.
Why not just write each value as many times as it was counted?
For plain numbers that works, and it is even simpler. But real data usually carries more than the key, such as a name with each score, and writing the counted keys would lose it. Moving the items themselves keeps everything attached.
Are my numbers sent anywhere?
No. The sort runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor