Counting Sort Visualization
Every comparison sort is stuck at n log n, but counting sort sidesteps the bound entirely by never comparing two elements. It uses values as array indices, which makes it linear — and also makes it completely unusable the moment your values are sparse or unbounded. Knowing exactly where that line sits is the useful part.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<int> countingSort(vector<int>& a, int maxVal) {
vector<int> count(maxVal + 1, 0);
for (int i = 0; i < (int)a.size(); i++) count[a[i]]++;
for (int v = 1; v <= maxVal; v++) count[v] += count[v - 1];
vector<int> out(a.size());
for (int i = (int)a.size() - 1; i >= 0; i--) {
count[a[i]]--;
out[count[a[i]]] = a[i];
}
return out;
}
int main() {
vector<int> a = {4, 2, 2, 8, 3, 3, 1};
vector<int> s = countingSort(a, 8);
for (int x : s) cout << x << ' ';
return 0;
}The stable version: prefix sums turn counts into end positions, and walking the input backwards preserves the original order of equal keys.
How it works, step by step
Values become indices
count[v] tallies how many times v appears. There is no comparison anywhere — the value itself selects the bucket, which is why the n log n lower bound does not apply. It is also why the value range, not just the element count, controls the cost.
Prefix sums turn tallies into positions
After the second loop, count[v] holds the number of elements <= v, which is exactly one past the last index where v belongs in the output. That single transformation is what upgrades a bucket tally into a placement plan.
Decrement then write
count[a[i]]-- moves the cursor from one-past-the-end to the actual slot, and that slot is then filled. The next element with the same value lands one position earlier, so equal values pack together from right to left.
The backwards scan buys stability
Because slots fill right to left, processing the input from the end means the last equal element gets the rightmost slot and the first gets the leftmost. Iterate forwards instead and equal elements come out reversed.
Cost is n plus k, not n log n
Two passes over n elements and two passes over the k+1 counters. When k is comparable to n this is genuinely linear; when k is a million and n is ten, you allocate a million counters to sort ten numbers.
Complexity
Linear only while k stays proportional to n — sorting values up to 10^9 needs a 10^9-entry counter array, so the algorithm degrades from fastest-available to unrunnable as the range grows, regardless of how few elements you have.
Common bugs
Sizing the count array to maxVal instead of maxVal + 1
count needs a slot for every value from 0 through maxVal inclusive. Off by one and the largest element writes past the end of the vector — undefined behaviour that frequently appears to work until the largest value shows up in your input.
Negative values crash it
count[a[i]]++ with a[i] = -3 indexes before the start of the vector. Counting sort assumes non-negative keys; for signed data, offset every value by -minVal on the way in and add it back on the way out, and size the counter array to maxVal - minVal + 1.
Iterating forwards and losing stability
Running the placement loop from i = 0 upward still sorts correctly but reverses equal elements. That only matters when you are sorting records by one field — and it matters enormously there, because radix sort is built on stable counting sort passes and silently produces garbage if this loop runs the wrong way.
Writing to out and then reading a[i] from the same array
If you try to make it in-place by writing back into a, you overwrite input you have not read yet and elements start duplicating. Counting sort fundamentally needs a separate output array once you want stability; watching values get clobbered mid-loop is the quickest way to see why.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How can counting sort be faster than O(n log n)?
The n log n lower bound applies only to sorts that determine order by comparing elements to each other. Counting sort never compares anything — it uses each value directly as an array index, extracting more information per operation than a yes/no comparison can. That extra power costs memory proportional to the value range.
When should I not use counting sort?
When the range of values is much larger than the number of elements. Sorting 100 integers that can each be up to a billion requires a billion-entry counter array, which is far worse than just calling a comparison sort. The rule of thumb is that k should be O(n) or smaller.
Why does counting sort iterate the input backwards?
To keep it stable. The prefix sums give each value the index just past its last output slot, and each placement decrements that cursor, so slots for a given value fill from right to left. Walking the input from the end means the last occurrence claims the rightmost slot, preserving the original relative order of equal elements.
Can counting sort handle negative numbers?
Not directly, since it uses values as array indices. Shift the data by subtracting the minimum value before counting and add it back when writing the output, sizing the counter array to maxVal - minVal + 1.