Overview
Counting Sort never compares two elements. It works out where every value belongs by counting how many times each key appears, which is why it escapes the O(n log n) lower bound that binds every comparison-based sort.
The trade is that it only applies to keys you can use as array indices: small non-negative integers, or anything mappable onto them. Sorting ages, exam scores, day-of-year or priority levels is where it shines; sorting arbitrary floats or strings is not what it is for.
How Counting Sort works
- Find the key range and allocate a count array of size k, where k is the number of distinct possible keys.
- Walk the input once, incrementing count[key] for each element.
- Turn the counts into running totals: each entry becomes the number of elements less than or equal to that key, which is exactly its end position in the output.
- Walk the input backwards, placing each element at output[count[key] − 1] and then decrementing that count.
- Copy the output back if the sort needs to happen in the original array.
When to use it
- Sorting integers with a known, modest range — ages, scores out of 100, ratings, HTTP status codes.
- As the inner pass of radix sort, where its stability is what makes the outer algorithm correct.
- Building a histogram and a sorted order in the same pass, since the count array is the histogram.
- A poor fit whenever k is large relative to n — sorting a thousand values spread across a billion possible keys allocates a billion buckets.
Complexity analysis
Time is O(n + k) in every case: one pass over n elements and one pass over k buckets, with no data-dependent branching. Space is O(k) for the counts plus O(n) for the output. The whole method hinges on k staying comparable to n — when k is much larger, both the memory and the bucket sweep dominate, and a comparison sort wins despite its log factor.
Frequently asked questions
Why walk the input backwards in the final step?
That is what makes the sort stable. Going backwards places the last occurrence of a key at the highest position it owns, so records that were already in relative order stay in that order. Walk forwards instead and equal keys come out reversed.
Does it work with negative numbers?
Yes, with an offset. Shift every key by −min so the smallest becomes index 0, then shift back when reading out. The count array size becomes max − min + 1.
Does it break the O(n log n) sorting lower bound?
It sidesteps rather than breaks it. That bound applies only to algorithms whose sole operation on keys is comparison. Counting sort uses the key as an address, which is extra information a comparison sort is not allowed to assume it has.