Counting Sort: Keys, Counts and Stability
Count how many times each key appears, turn those counts into starting positions, then place each value directly where it belongs.
How Counting Sort Works
Counting sort breaks the rule that every other sort on this course obeys: it never compares two values. That is how it escapes the O(n log n) lower bound, which applies only to algorithms that learn about order through comparisons. Instead it uses each value directly as an array index, which is possible whenever the keys are integers in a known, bounded range.
- Find the key range scan once for the minimum and maximum, so a count array of size k = max − min + 1 can be allocated.
- Count each key walk the input and increment
count[value − min], so every key knows how many times it occurs. - Make the counts cumulative add each count to the one before it, so every key knows the slot just past its last position.
- Place values backwards walk the input from right to left, decrement that key's counter, and write the value at the slot it lands on.
- Read off the output the output array is now sorted, built without a single comparison between two input values.
- The value is the index — this is the whole trick
- Counting is O(n); building positions is O(k)
- The backward placement pass is what preserves stability
- Works on integers, or anything with a bounded integer key
Why the Last Pass Runs Backwards
The placement loop reads the input from the last element to the first, and that detail is the single most commonly missed part of the algorithm. Running it forwards still sorts correctly — the output is in non-decreasing order either way — but it silently reverses the relative order of equal keys, and that destroys stability.
Stability matters whenever a sort is used as a stage rather than an end. Sorting records by city and then by name only produces a correct final order if the second sort preserves the first ordering within ties. It is also why radix sort requires a stable per-digit sort: radix sort makes several counting-sort passes, and if any pass reordered equal digits, every earlier pass would be undone.
The mechanism is straightforward once seen. Each key's counter holds the slot just past its last position, and the loop decrements it before writing, so slots are handed out from the highest downwards. Feeding the input backwards means the last equal value claims the highest slot, the second-to-last claims the one below it, and the original left-to-right order survives.
- Forwards is still sorted, but no longer stable
- Positions are consumed high-to-low as the counter decrements
- Radix sort is only correct because each digit pass is stable
- Stability is what makes multi-key sorting possible
Sort with counting sort
def counting_sort(values):
if not values:
return values
low, high = min(values), max(values)
counts = [0] * (high - low + 1)
for value in values:
counts[value - low] += 1
# Cumulative counts, so counts[k] is one past the last slot for key k.
for key in range(1, len(counts)):
counts[key] += counts[key - 1]
output = [0] * len(values)
# Backwards with a pre-decrement, so equal keys keep their order.
for value in reversed(values):
counts[value - low] -= 1
output[counts[value - low]] = value
return output
print(counting_sort([2, 5, 3, 2, 5, 2]))#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Counting sort: the value is the index, so nothing is ever compared.
vector<int> countingSort(const vector<int>& values) {
if (values.empty()) return values;
int low = *min_element(values.begin(), values.end());
int high = *max_element(values.begin(), values.end());
vector<int> counts(high - low + 1, 0);
for (int value : values) counts[value - low]++;
// Cumulative counts, so counts[k] is one past the last slot for key k.
for (int key = 1; key < (int)counts.size(); key++) counts[key] += counts[key - 1];
vector<int> output(values.size());
// Backwards with a pre-decrement, so equal keys keep their order.
for (int i = (int)values.size() - 1; i >= 0; i--) {
counts[values[i] - low]--;
output[counts[values[i] - low]] = values[i];
}
return output;
}
int main() {
vector<int> values = {2, 5, 3, 2, 5, 2};
for (int v : countingSort(values)) cout << v << " ";
cout << endl;
return 0;
}import java.util.Arrays;
public class CountingSort {
// Counting sort: the value is the index, so nothing is ever compared.
static int[] countingSort(int[] values) {
if (values.length == 0) return values;
int low = Arrays.stream(values).min().getAsInt();
int high = Arrays.stream(values).max().getAsInt();
int[] counts = new int[high - low + 1];
for (int value : values) counts[value - low]++;
// Cumulative counts, so counts[k] is one past the last slot for key k.
for (int key = 1; key < counts.length; key++) counts[key] += counts[key - 1];
int[] output = new int[values.length];
// Backwards with a pre-decrement, so equal keys keep their order.
for (int i = values.length - 1; i >= 0; i--) {
counts[values[i] - low]--;
output[counts[values[i] - low]] = values[i];
}
return output;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(countingSort(new int[]{2, 5, 3, 2, 5, 2})));
}
}Step through it
Running on [2, 5, 3, 2, 5, 2]
When k Makes It Unusable
The cost is O(n + k) in both time and space, and that second term decides whether the algorithm is brilliant or unusable. Sorting a million exam scores in the range 0–100 is close to ideal: k is 101, the work is essentially linear, and no comparison sort comes near it. Sorting a million 32-bit integers with the same code allocates an array of four billion counters, which is not merely slow but impossible.
The rule of thumb is that counting sort pays when k is O(n). When the range is large but the values are sparse, the answer is usually not counting sort but radix sort, which applies counting sort to one small digit at a time and so replaces a huge k with several tiny ones.
The other constraint is that keys must be integers, or map onto integers. Floating-point values, strings and arbitrary objects have no natural array index, which is where bucket sort takes over — it distributes values into ranges rather than exact slots.
| Input | n | k | Verdict |
|---|---|---|---|
| Exam scores 0–100 | 1,000,000 | 101 | Ideal — effectively O(n) |
| Ages 0–120 | 50,000 | 121 | Ideal |
| 32-bit integers | 1,000,000 | 4.3 billion | Impossible — use radix sort |
| Floating-point values | 1,000,000 | unbounded | No integer key — use bucket sort |
- O(n + k) time and O(n + k) space
- Worth it when k is O(n), disastrous when k is huge
- Large sparse ranges are radix sort's problem, not counting sort's
- Non-integer keys need bucket sort instead
On Paper: Sorting [2, 5, 3, 2, 5, 2]
Sort [2, 5, 3, 2, 5, 2] by hand, tracking the three arrays. Keys run from 2 to 5, so k = 4 and the count array is indexed by the values 2, 3, 4 and 5.
- Input:
[2, 5, 3, 2, 5, 2] - Keys: 2 to 5, so k = 4
- Counting: occurrences per key, then running totals
Counting gives [3, 1, 0, 2] — three 2s, one 3, no 4s, two 5s. Made cumulative that becomes [3, 4, 4, 6]: the 2s end at 3, the 3 ends at 4, and the 5s end at 6. Note that the count for 4 is zero, so it occupies no output space at all while still carrying a position.
Placing backwards, the last input value is 2. Its counter drops from 3 to 2, so this 2 lands at index 2 — the third slot — and the earlier 2s take indexes 1 and 0 in turn. That is the stability mechanism working: the leftmost 2 in the input ends up leftmost in the output.
- Counts
[3, 1, 0, 2]become cumulative[3, 4, 4, 6] - A key with count 0 takes no output space but still carries a position
- Placement runs right-to-left so equal keys keep their order
- Six placements, no comparisons, output
[2, 2, 2, 3, 5, 5]