How counting sort works
Every sort you have seen so far decides the order by comparing two values. Counting sort never does. It uses each value as an index into an array of counters. Think of sorting a stack of exam papers by grade: you do not compare papers with each other, you drop each one into the tray for its grade and then stack the trays in order.
Count. Find the smallest and largest value, low and high, and make one counter for every value in between: k = high − low + 1 counters. Walk the array once and add 1 to the counter of each value. Subtracting low is what lets negative numbers work: the value low uses counter 0.
Running totals. Add each counter to the one after it. Now the counter for value v holds how many values are ≤ v, which is exactly one past the last position v will occupy in the sorted output. In the CLRS example below, the counter for 3 becomes 7, so the three 3s end at index 6.
Place, from the right. Walk the input from its last element to its first. For each value, take one off its counter and write the value to that index of out. Walking right to left means the last of several equal values gets the last slot, so equal values keep their original order. That property, stability, is why counting sort can be the digit pass inside radix sort. Finally, copy out back.
The algorithm in 5 steps
- 1 Find
lowandhighand makehigh − low + 1counters, all 0. - 2 For each value
v, add 1 tocount[v − low]. - 3 Running totals: for
dfrom 1 up,count[d] += count[d − 1]. Nowcount[d]is the number of values ≤low + d. - 4 Walk the input from right to left: take 1 off the value's counter and write the value to
outat that index. - 5 Copy
outback into the array.
Worked example
This is the array from Figure 8.2 of CLRS (Introduction to Algorithms), run through the same code as the visualizer. The first row is the count array after counting, the second after the running totals. Each row after that places one value into out, walking the input from the right. The final copy back into the array is counted in the total but not listed.
Input: [2, 5, 3, 0, 2, 3, 0, 3]
- Step 9 Read 3 (index 7): the counter for 3 goes up to 3. count 200122330415
- Step 14 The counter for 5 becomes 8: 8 values are ≤ 5. Each counter now says where the last copy of its value ends in the sorted output. count 202142737485
- Step 16 Write 3 to out[6]. out ······3·
- Step 18 Write 0 to out[1]. out ·0····3·
- Step 20 Write 3 to out[5]. out ·0···33·
- Step 22 Write 2 to out[3]. out ·0·2·33·
- Step 24 Write 0 to out[0]. out 00·2·33·
- Step 26 Write 3 to out[4]. out 00·2333·
- Step 28 Write 5 to out[7]. out 00·23335
- Step 30 Write 2 to out[2]. Every value is placed: out is sorted. out 00223335
Total for this run: 21 counter updates and 16 writes, in 39 animation steps. Result: 0, 0, 2, 2, 3, 3, 3, 5.
Time and space complexity
Best
O(n + k)There is no best case: it makes the same fixed passes over the n values and the k counters, whatever the order of the input. k is the number of possible values, high − low + 1.
Average
O(n + k)The same fixed passes. When k is no bigger than a constant times n, that is O(n): linear time.
Worst
O(n + k)Still linear in n, but k can dominate: two values, 0 and 1,000,000, need a million counters to sort two numbers.
Space
O(n + k)The count array (k entries) plus the output array (n entries). It does not sort in place.
- Stable:
- Yes
- In place:
- No
- Comparison sort:
- No
- Works on:
- Integer keys in a small range
Same 8 numbers, comparison sorts vs counting sort
Every comparison sort needs at least ⌈log₂(n!)⌉ comparisons in the worst case, 16 for 8 values, and that grows like n log n. Counting sort never compares two values to order them: on the visualizer's numbers it runs one counting pass, with 21 counter updates and 16 writes. Computed from the code on these pages, not typed in.
| Algorithm | Comparisons | Other work |
|---|---|---|
| Counting sort | 0 (after finding the smallest and largest) | 21 counter updates, 16 writes |
| Merge sort | 17 | 24 writes |
| Quick sort | 39 | 9 swaps |
| Heap sort | 24 | 16 swaps |
| Insertion sort | 19 | 13 shifts |
Fewer operations on 8 numbers is not the point; the growth is. Comparison sorts grow like n log n. Counting sort grows like n + k, where k is the number of possible values, so it wins only while k stays small.
When to use it, and when not to
Good fit
- The keys are integers in a small range: exam scores 0 to 100 (101 counters), ages 0 to 120, star ratings 1 to 5, bytes 0 to 255. Then it beats any comparison sort, because it is O(n) and makes no comparisons.
- You need the per-digit pass of radix sort. Radix sort runs counting sort once per digit with k = 10 (or k = 256 per byte), and it only works because counting sort is stable.
- You are sorting records by a small integer key and must keep the original order of equal keys, such as orders by priority 1 to 5 where earlier orders stay first.
- You need the frequencies anyway. The count array after step 2 is a histogram, which solves "most frequent element" or "is this an anagram" questions in the same pass.
Pick something else when
- The range is large compared with n. Sorting 1,000 values that lie between 0 and 10⁹ would need a billion counters, about 4 GB as 32-bit ints. Use radix sort or a comparison sort.
- The keys are not integers: floats, strings or objects compared by a custom rule. They cannot be used as array indices directly. Map them to small integers first, or use a comparison sort.
- Memory is tight. Counting sort needs O(n + k) extra space; heap sort sorts in place with O(1).
- The data is tiny or almost sorted. Insertion sort or your language's built-in sort is simpler and just as fast there.
Common mistakes and bugs
-
1.Forgetting the offset for negative values
Without
− low, a value of −3 indexescount[−3]. Java throws ArrayIndexOutOfBoundsException, but Python silently readscount[-3]as the third counter from the end, so the program runs and the output is wrong. Always size the array ashigh − low + 1and index withv − low. -
2.Placing left to right
With running totals, each counter points one past the last slot of its value. Walking the input from the left and filling from those positions puts the first of two equal values in the later slot, which reverses equal values. On plain integers you cannot see it; inside radix sort it gives a wrong answer.
-
3.Writing before decrementing
After the running totals,
count[d]equals the number of values ≤ that value, which is one past the last index. Writing toout[count[d]]first and decrementing after writes one place too far right, and the last value runs off the end ofout. Decrement first, as the code here does. -
4.Rebuilding values from the counts when there is data attached
The short version, "for each value v, write v count[v] times", is fine for bare integers. It is not a stable sort of records: if you are sorting students by grade, it rebuilds grades and loses which student had which. Use the running-total version, which moves the original items.
-
5.Using it on a wide range because it is "O(n)"
O(n + k) hides k. Sorting ten phone numbers by value would need 10¹⁰ counters. Check that k is no bigger than a small multiple of n before choosing counting sort.
Interview questions
Try answering before you open the model answer.
Q1 Comparison sorts need Ω(n log n) comparisons. How does counting sort run in O(n)?
Model answer: The lower bound only applies to algorithms that learn about the order by comparing pairs of elements: there are n! possible orders, and each yes/no comparison can at best halve them, so log₂(n!) ≈ n log₂ n comparisons are needed. Counting sort uses each value as an array index instead, so the bound does not apply. The price is that keys must be small integers.
Q2 Why does the placing loop walk from right to left?
Model answer: After the running totals, each counter points one past the last slot of its value, and we fill slots from that end backwards. Visiting the input from the right means the last occurrence of a value gets the last slot and earlier occurrences get earlier slots, so equal values keep their order. That stability is what radix sort relies on.
Q3 Sort one million exam scores, each between 0 and 100.
Model answer: Counting sort with 101 counters: one pass to count, 100 additions for the running totals, one pass to place. That is about three million simple steps (count, place, copy back) and 101 extra integers plus the output, versus roughly 20 million comparisons for an O(n log n) sort. If you only need the scores and not who scored them, you can even skip the output array and rewrite from the counts.
Q4 Sort an array that contains only 0s, 1s and 2s.
Model answer: Counting sort works: count the three values, then write that many 0s, 1s and 2s. That is two passes and O(1) extra space. The follow-up is usually "in one pass": Dijkstra's Dutch national flag partition, with three pointers low, mid and high, swaps values into place in a single scan.
Q5 When would you pick radix sort over counting sort?
Model answer: When the range of values is large. Counting sort needs a counter for every possible value, so 32-bit integers would need about 4.3 billion counters. Radix sort runs counting sort on one digit at a time, so each pass needs only 10 counters (or 256 per byte): four byte passes cover any 32-bit integer.
Frequently asked questions
What is the time complexity of counting sort?
O(n + k), where n is the number of values and k is the size of their range, high − low + 1. It is the same for every input order: one pass to count, one over the counters for running totals, one to place. When k is at most a constant times n, that is linear time, O(n).
Is counting sort stable?
Yes, in the running-total version shown here. It walks the input from right to left and fills each value's slots from the back, so equal values come out in their original order. The shortcut version that rewrites values from the counts has no notion of the original items, so it cannot keep records in order.
Can counting sort handle negative numbers?
Yes, by shifting. Find the smallest value, low, and store the count of v at index v − low. The array then needs high − low + 1 counters and the rest of the algorithm is unchanged. The code on this page does exactly that, which is why the visualizer accepts negative numbers.
Why is counting sort not used for everything if it is O(n)?
Because the hidden term k can be huge. Sorting a few numbers spread between 0 and a billion would need a billion counters. It also needs integer keys and O(n + k) extra memory. It shines on small ranges, such as scores, ages, bytes or characters, and as the digit pass inside radix sort.
Is counting sort a comparison sort?
No. It never compares two elements to decide which goes first; each value is used as an index into the count array. That is how it beats the Ω(n log n) lower bound for comparison sorts. The code here only compares while finding the smallest and largest value, a single scan before sorting starts.