Counting Sort Explained
Counting Sort sorts integers in O(n + k) linear time without comparisons. Learn how it works, when it beats Quick Sort, and its memory trade-offs.
On this page +
Counting Sort is a non-comparison algorithm that sorts integers in linear O(n + k) time, where k is the range of values. Instead of comparing elements, it counts how many times each value appears and uses those counts to place every element directly into its final position.
How Counting Sort works #
First, count occurrences of each value into a count array indexed by value. Then compute a running (prefix) sum so each entry tells you the final position of that value. Finally, walk the input from right to left, placing each element at its computed position and decrementing the count — which keeps the sort stable.
Why it beats O(n log n) #
Counting Sort never compares two elements, so the comparison-sort lower bound does not apply to it. For data like exam scores (0-100) or ages, where k is small, it sorts in true linear time — far faster than Quick or Merge Sort.
The catch: memory and range #
Counting Sort needs O(k) memory for the count array. If you have 100 values ranging up to 10 million, you would allocate 10 million slots — wasteful and slow. It only works on integers (or data mappable to integers) with a modest range. For larger ranges, Radix Sort applies Counting Sort digit by digit to keep k small.
Frequently asked questions
What is the time complexity of Counting Sort? +
When should you use Counting Sort? +
Why isn't Counting Sort used everywhere if it's O(n)? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.