Counting Sort Algorithm
The counting sort algorithm sorts integers without comparing them: it counts how many times each value appears, then writes the values back in order. When the range of values is small, it runs in linear time. Step through it below, then read how it works and its limits.
Try it: Works for small integers (here 0 to 9). Count how many times each value appears, then write the values back in order using those counts. No comparisons are needed. Click the Next button to perform one step at a time.
Time: O(n + k) where k is the value range · Space: O(n + k) · Stable
What is Counting Sort?
Counting Sort is a non-comparison sort for integers in a small range. It counts how many times each value occurs, turns the counts into positions, and places each element directly in its final spot.
Key insight: Because it never compares elements, it can beat the O(n log n) limit of comparison sorts. The catch is that it needs memory proportional to the value range k, so it only pays off when k is not much larger than n.
Counting Sort Time Complexity
| Measure | Value |
|---|---|
| Best case | O(n + k) |
| Average case | O(n + k) |
| Worst case | O(n + k) |
| Space | O(n + k) |
| Stable | Yes (with the prefix-sum version) |
For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for counting sort.
Algorithm Steps
- Find the maximum value k.
- Create a count array of size k + 1 filled with zeros.
- Count the occurrences of every value.
- Convert counts into running totals (positions).
- Walk the input backwards, placing each value at its position and decrementing its count.
Advantages and Disadvantages
Advantages
- Linear time O(n + k) when the range k is small
- Stable when implemented with prefix sums
- Simple and very fast for suitable data
Disadvantages
- Only works for integers (or values that map to small integers)
- Wastes memory when the value range is large
- Needs O(n + k) extra space
Real-World Applications
- Sorting small integer keys such as ages, grades or scores
- As the stable digit sorter inside Radix Sort
- Histograms and frequency analysis
- Sorting characters in strings (small alphabet)
When to Use Counting Sort
Use it when keys are integers in a small known range, such as 0 to 100. If the range is huge, use Radix Sort or a comparison sort.
Counting Sort Implementation
Python
def counting_sort(arr):
if not arr:
return arr
k = max(arr) + 1
count = [0] * k
for x in arr: # count occurrences
count[x] += 1
for i in range(1, k): # prefix sums = end positions
count[i] += count[i - 1]
out = [0] * len(arr)
for x in reversed(arr): # backwards keeps it stable
count[x] -= 1
out[count[x]] = x
return outJavaScript
function countingSort(arr) {
if (arr.length === 0) return arr;
const k = Math.max(...arr) + 1;
const count = new Array(k).fill(0);
for (const x of arr) count[x]++; // count occurrences
for (let i = 1; i < k; i++) count[i] += count[i - 1]; // prefix sums
const out = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) { // backwards keeps it stable
out[--count[arr[i]]] = arr[i];
}
return out;
}FAQ
What does k mean in O(n + k)?
k is the size of the value range (maximum minus minimum, plus one). Counting sort needs one counter per possible value, so it is fast when k is small relative to n and wasteful when values are spread widely, for example sorting 10 numbers between 0 and a billion.
Can counting sort handle negative numbers?
Yes. Subtract the minimum value from every key before counting (so the smallest becomes 0), then add it back when writing the output.
How can counting sort beat the O(n log n) limit?
The O(n log n) lower bound only applies to sorts that work by comparing elements. Counting sort uses the values themselves as array indices instead. It is also the stable digit-sorting step inside Radix Sort.
