Counting Sort: Counting Each Value, Then Placing It

Count how often each value occurs, turn the counts into positions, then copy each item to its place.

Counting sort is a sorting algorithm for integer keys in a small range: it counts how many times each value occurs, turns the counts into the positions each value ends at, and copies every item straight to its place in a new array. This card walks through the three steps, shows why the copy runs from the last item backwards, and gives its cost.

The first step makes a count array with one cell per possible key value, all zero, and walks the input adding one to the cell for each item's key. The second step replaces each cell with the sum of itself and every cell before it, a running total called a prefix sum. The cell for a value then holds the number of items whose key is no larger than that value, which is one past the last index that value may take in the output. The third step walks the input once more, from the last item to the first, and for each item takes one from its key's cell and writes the item at the index that leaves. The items are never compared with each other.

The trace sorts 13 4 10 7 14 3 10, whose keys run from 0 to 14, so the count array has 15 cells. Each counting frame marks the cell the key adds to, and the last frame shows the cells after the prefix sums.

Counting sort's count array on 13 4 10 7 14 3 10

Input13 4 10 7 14 3 10

Start
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 0
9. 0
10. 0
11. 0
12. 0
13. 0
14. 0
15. 0
The keys run from 0 to 14, so the count array has 15 cells, one per value, and every cell starts at zero. A cell's index is the value it counts.
Count 13
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 0
9. 0
10. 0
11. 0
12. 0
13. 0
14. 1key
15. 0
13 adds one to cell 13.
Count 4
1. 0
2. 0
3. 0
4. 0
5. 1key
6. 0
7. 0
8. 0
9. 0
10. 0
11. 0
12. 0
13. 0
14. 1
15. 0
4 adds one to cell 4.
Count 10
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 0
8. 0
9. 0
10. 0
11. 1key
12. 0
13. 0
14. 1
15. 0
10 adds one to cell 10.
Count 7
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 0
8. 1key
9. 0
10. 0
11. 1
12. 0
13. 0
14. 1
15. 0
7 adds one to cell 7.
Count 14
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 0
8. 1
9. 0
10. 0
11. 1
12. 0
13. 0
14. 1
15. 1key
14 adds one to cell 14.
Count 3
1. 0
2. 0
3. 0
4. 1key
5. 1
6. 0
7. 0
8. 1
9. 0
10. 0
11. 1
12. 0
13. 0
14. 1
15. 1
3 adds one to cell 3.
Count 10
1. 0
2. 0
3. 0
4. 1
5. 1
6. 0
7. 0
8. 1
9. 0
10. 0
11. 2key
12. 0
13. 0
14. 1
15. 1
The second 10 adds one to cell 10, which now holds 2.
End positions
1. 0
2. 0
3. 0
4. 1
5. 2
6. 2
7. 2
8. 3
9. 3
10. 3
11. 5
12. 5
13. 5
14. 6
15. 7
Each cell becomes the sum of itself and every cell before it: the number of items no larger than its value, which is one past the last index that value may take. Walking the input from the last item, each item takes one from its cell and lands at the index left there, so the second 10 goes to index 4 and the first to index 3. The output is 3 4 7 10 10 13 14.

Result3 4 7 10 10 13 14

The final frame says that 3 ends before index 1, that 4 ends before index 2, and that both 10s end before index 5, at indices 3 and 4. The empty cells between them cost a step each and place nothing, which is the k in the sort's cost.

The backwards walk is what makes counting sort stable, which means items with equal keys come out in the order they went in. Each value's cell counts down from the end of that value's block, so the last 10 in the input takes the last slot for 10 and the first 10 takes the slot before it. A run tagged the two 10s as 10a and 10b. Placing from the last item gave 3 4 7 10a 10b 13 14; placing from the first item into the same end positions gave 10b before 10a. Stability matters little for bare numbers, and a great deal for records sorted by one field, and it is the property radix sort is built on.

Counting sort is not a fit when the range is wide. A million 64-bit identifiers would need 2⁶⁴ counters, about 1.8 × 10¹⁹, however few items there are; a comparison sort, or radix sort, is the tool there.

Counting sort on n integer keys in a range of k values

Best, average and worst case: O(n + k); two passes over the items and two over the counters, whatever the order
Extra space: O(n + k); k counters and an output array of n items
Stable: Yes; when the items are placed from the last to the first
In place: No; the items are copied into a second array

The sign to reach for counting sort is integer keys, or keys that map to integers, in a range not much larger than the number of items: exam marks from 0 to 100, ages in years, temperatures in whole degrees, letters of an alphabet. When k is about n or smaller, O(n + k) is O(n). When k is far larger than n, the counters dominate and the sort stops being fast.

On the Algorithms: Efficient Sorting cheatsheet

← → move through sections and cards