Counting sort
mediumTally the values, turn the tallies into positions with a prefix sum, then place each element directly. The comparison counter stays at zero for the whole run - this is not bound by the Ω(n log n) lower bound.
O(n + k)Average O(n + k)Worst O(n + k)Space O(n + k)StableNeeds extra memorySaved in this browser - no sign-up, nothing sent anywhere.
How counting sort works
No element is ever compared with another - the value itself is the address. With values known to lie in 0..k, allocate k + 1 counters and tally: count[v] is how many times v appears. This visualizer's default is 12 values in 0..9, so ten counters. The comparison counter stays at zero all run, which is how counting sort escapes the Ω(n log n) lower bound - that bound only binds sorts that compare.
The clever step is the prefix sum: turning each count into a running total makes count[v] equal the number of elements <= v - which is exactly one past the slot where the last v belongs. The histogram has become a placement table. Then walk the input backwards, decrement count[v], and write v at the resulting index: each element lands in its final position in one step.
Backwards plus decrement is what makes it stable - the last copy of v claims the highest slot, the copy before it the next one down, preserving input order among equals. The cost is O(n + k) time and space, and k is the catch: 0..9 needs ten counters, but a dozen arbitrary 32-bit integers would need four billion. Small, known range or nothing - and that stability is why it becomes radix sort's inner engine.
Step by step
- Sort [4, 2, 7, 1, 3, 7, 2, 5, 0, 6, 3, 1] - twelve values in 0..9. Tally them: count = [1, 2, 2, 2, 1, 1, 1, 2, 0, 0].
- Prefix-sum the counts into [1, 3, 5, 7, 8, 9, 10, 12, 12, 12]. Now count[3] = 7 means seven values are <= 3.
- Walk the input backwards, starting at a[11] = 1: decrement count[1] to 2 and place the 1 at out[2].
- a[10] = 3: count[3] drops to 6, so the 3 lands at out[6]. Every placement is arithmetic - still zero comparisons.
- The two 7s show the stability: the walk meets a[5] first and places it at out[11], then a[2] at out[10] - input order preserved.
- After twelve placements, out = [0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 7]. Sorted without a single comparison.
Complexity
| Best case time | O(n + k) |
|---|---|
| Average time | O(n + k) |
| Worst case time | O(n + k) |
| Space | O(n + k) |
k is the size of the value range, which is why it must be small.
Reference implementation
Python
def counting_sort(a, k=None):
if not a:
return a
k = k or max(a)
count = [0] * (k + 1)
for x in a:
count[x] += 1
for i in range(1, k + 1): # prefix sums -> end positions
count[i] += count[i - 1]
out = [0] * len(a)
for i in range(len(a) - 1, -1, -1): # backwards keeps it stable
count[a[i]] -= 1
out[count[a[i]]] = a[i]
return outJavaScript
function countingSort(a, k = Math.max(...a)) {
const count = new Array(k + 1).fill(0);
for (const x of a) count[x]++;
for (let i = 1; i <= k; i++) count[i] += count[i - 1];
const out = new Array(a.length);
for (let i = a.length - 1; i >= 0; i--) { // backwards keeps it stable
out[--count[a[i]]] = a[i];
}
return out;
}Worth noticing
No comparisons at all
The comparison counter stays at zero for the whole run. Counting sort is not bound by the Ω(n log n) comparison lower bound because it never compares two elements - it uses the values themselves as array indices.
The prefix sum is the clever bit
After counting, count[v] is 'how many values are ≤ v', which is exactly the position just past where the v's belong. That single pass converts a histogram into a placement table.
Why the last loop runs backwards
Walking the input right-to-left and decrementing before placing keeps equal elements in their original relative order. Run it forwards and counting sort is still correct but no longer stable - which breaks radix sort, since radix sort depends on this stability.
O(n + k), and k can bite
The cost includes the size of the value range. Sorting a dozen 32-bit integers would allocate four billion counters. That is why the range must be small and known.
Common pitfalls
- Allocating count with size k instead of k + 1 - the maximum value writes one past the end. The range 0..9 needs ten slots, not nine.
- Forgetting negative values index below zero. Shift by the minimum first, making the range 0..max - min, or the tally corrupts memory.
- Running the placement pass forwards. The output is still sorted, but equal elements reverse - and radix sort built on top silently produces wrong answers.
- Using it when the range dwarfs the data: 1,000 values spread over 0..10^9 means a billion-slot count array doing nothing. The k in O(n + k) is real cost.
- Rebuilding output straight from the histogram - emit v, count[v] times - works for bare integers but destroys the original records; the prefix-sum pass exists to move whole elements with their payloads.
Where it is used
- The per-digit sub-sort inside LSD radix sort - chosen precisely because it is stable and linear.
- Histogram-shaped data: sorting bytes, exam scores 0..100, ages, or pixel intensities in one pass.
- Bucketing by small enumerations - grouping records by status code or category before per-group processing.
- The interview answer to sorting in O(n): spot the bounded integer range, then say counting sort.
Frequently asked questions
What is the time and space complexity of counting sort?
O(n + k) time in every case - one pass to tally, one over the k counters for prefix sums, one backwards pass to place - where k is the size of the value range. Space is also O(n + k): the count array plus a separate output array, so it is not in place.
Why does counting sort walk the input backwards?
For stability. After the prefix sums, count[v] points just past the last slot owned by value v. Decrementing before placing hands the highest slot to the latest copy in the input, the next slot down to the copy before it - so equal values keep their original order. A forward walk reverses them.
Can counting sort handle negative numbers?
Yes, with an offset. Find the minimum, index the count array by v - min, and the range becomes 0..max - min. The cost formula keeps the same shape with k = max - min + 1 - which also warns you: a huge spread between min and max makes the counter array huge too.
If counting sort is O(n), why is it not the default sort?
Because of k and because of keys. The O(n + k) bound explodes when the value range is large - 32-bit integers would need four billion counters. And it only works on integer-like keys that can index an array: no floats, no strings, no custom comparators. General-purpose sorts trade speed for none of those restrictions.