Algorithms
Counting Sort
O(n + k) time, where k is the range of possible values · O(k) space for the count bins. This is not a comparison sort like the ones above.
The idea, in plain English
Counting sort tallies exam scores into labeled bins instead of comparing papers to each other. You count how many times each score appears, then read the bins off in order. It never compares two items directly — it just counts.
How it works
- 1Find the biggest value in the list, so you know how many bins you need.
- 2Make a bin, a count, for every possible value from 0 up to that biggest value. Count how often each value shows up.
- 3Walk through the bins in order from smallest to largest. Write out each value as many times as it was counted.
When you'd use it
Use it to sort non-negative whole numbers with a small range — like ages, grades, or dice rolls. It can beat other sorts by never comparing items at all.
Common beginner mistakes
- Using it on data with a huge range, like arbitrary decimals or huge numbers. The bin array becomes enormous.
- Forgetting it only works on non-negative whole numbers, unless you adjust it for negative numbers.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Before: 5 2 9 1 5 6
Sorted: 1 2 5 5 6 9See it in motion
Two phases: tally values into bins, then read the bins in order. No comparisons.
Not sure this is the right topic? See the learning paths → or where this leads →