Counting Sort Stability: Why Prefix Sums and Right-to-Left Placement Work
How stable counting sort keeps equal keys in their original order using prefix-sum end pointers and a right-to-left placement pass, with a worked walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Plain counting sort is easy: tally how many times each value appears, then re-emit each value that many times. But that trick only works when the elements are their keys. The moment your array holds records sorted by one field — orders by price, students by score — you need stability: equal keys must come out in the same order they went in.
Getting counting sort to be stable takes two precise moves that look almost arbitrary until you see why: turn the count array into prefix sums, then fill the output by scanning the input right to left. Skip either one and equal keys scramble.
This walks through the exact algorithm the Counting Sort - Stable - Logic visualizer animates, and proves why those two choices are the whole game.
The problem
Sort an array of non-negative integers into ascending order. When two elements share a value, they must appear in the output in the same relative order they had in the input — that is what makes the sort stable.
To see stability, tag each duplicate with a subscript for its input position. 4, 2ₐ, 2ᵦ, 8, 3ₐ, 3ᵦ, 1:
Input: [4, 2ₐ, 2ᵦ, 8, 3ₐ, 3ᵦ, 1]
Output: [1, 2ₐ, 2ᵦ, 3ₐ, 3ᵦ, 4, 8]Both 2s and both 3s stay in a-before-b order. A stable sort guarantees that; an unstable one might hand you 2ᵦ, 2ₐ and you would never notice on bare integers — but you would on the records they represent.
The brute force baseline
The naive counting sort tallies frequencies, then rebuilds the array by walking the buckets and emitting each value as many times as it was counted.
function countingSortNaive(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (const x of arr) count[x]++;
const out = [];
for (let v = 0; v < count.length; v++) {
for (let c = 0; c < count[v]; c++) out.push(v); // emit v, count[v] times
}
return out;
}For raw integers this returns the right multiset in O(n + k) time. The problem is the out.push(v) line: it fabricates a fresh v instead of moving the actual element that had value v. There is no way to know which original 2 you are emitting first, so any satellite data riding along is lost, and the sort is not stable. To carry real elements you need each one routed to a specific destination slot — and that is what prefix sums compute.
The key insight: prefix sums are end pointers
Start from the frequency array and run a prefix-sum sweep, count[i] += count[i - 1]. This quietly changes what every slot means.
Before the sweep, count[v] answers "how many vs are there?" After it, count[v] answers "how many elements are ≤ v?" — which is exactly the number of output slots occupied by everything up to and including v. So count[v] becomes the index one past the last slot reserved for value v. Subtract 1 and you have the last slot where a v belongs.
That single number is the destination. Every element of value v must land in the block ending at count[v] - 1. To place several vs without collision, decrement count[v] after each placement so the next v fills the slot just to the left.
Now the stability move falls out. If you place the last v in the input first, it takes the rightmost slot in the block; the earlier v placed later takes a slot to its left. Walking the input right to left therefore lays equal keys down back-to-front into a block that fills back-to-front — and the two reversals cancel, preserving original order. Reverse the scan direction and you would reverse every group of duplicates.
The optimal solution
function countingSortStable(arr) {
let max = Math.max(...arr);
let count = new Array(max + 1).fill(0);
for (let x of arr) {
count[x]++;
}
for (let i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
let sortedArr = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
let x = count[arr[i]];
sortedArr[x - 1] = arr[i];
count[arr[i]]--;
}
return sortedArr;
}Three passes, each doing one job. The first pass tallies frequencies. The second converts those frequencies into end pointers with a prefix sum. The third pass reads the input from the last index down to the first, and for each element arr[i] looks up its pointer x = count[arr[i]], drops the element into sortedArr[x - 1], then decrements the pointer so the next equal key goes one slot left. Because we move arr[i] itself — not a freshly minted value — any satellite data comes along, and the right-to-left order keeps duplicates stable.
Walkthrough
Take the smaller input [1ₐ, 3, 1ᵦ, 2] so every step fits on screen.
Pass 1 — tally. After counting frequencies, count = [0, 2, 1, 1] (two 1s, one 2, one 3).
Pass 2 — prefix sum. Sweeping count[i] += count[i - 1]:
| i | before | count[i-1] | after | count |
|---|---|---|---|---|
| 1 | 2 | 0 | 2 | [0, 2, 1, 1] |
| 2 | 1 | 2 | 3 | [0, 2, 3, 1] |
| 3 | 1 | 3 | 4 | [0, 2, 3, 4] |
Now count = [0, 2, 3, 4] — each slot is the index one past the last home of that value.
Pass 3 — place, scanning i from 3 down to 0. slot = count[arr[i]] - 1.
| i | arr[i] | count[value] | slot | after count | sortedArr |
|---|---|---|---|---|---|
| 3 | 2 | 3 | 2 | [0, 2, 2, 4] | [_, _, 2, _] |
| 2 | 1ᵦ | 2 | 1 | [0, 1, 2, 4] | [_, 1ᵦ, 2, _] |
| 1 | 3 | 4 | 3 | [0, 1, 2, 3] | [_, 1ᵦ, 2, 3] |
| 0 | 1ₐ | 1 | 0 | [0, 0, 2, 3] | [1ₐ, 1ᵦ, 2, 3] |
Watch the two 1s. 1ᵦ (input index 2) is reached first by the right-to-left scan and takes slot 1; 1ₐ (input index 0) comes later and takes slot 0. Output order is 1ₐ, 1ᵦ — exactly the input order. Stability holds.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n + k) | n for the tally, k for the prefix sweep, n for placement — no comparisons, k = max + 1 |
| Space | O(n + k) | the length-k count array plus a length-n sortedArr output buffer |
Counting sort beats the O(n log n) comparison-sort floor precisely because it never compares elements — it addresses them by value. That only pays off when k is on the order of n. If the values range up to a billion, k dominates and the algorithm becomes both slow and memory-hungry.
Common mistakes
- Placing left to right. Scanning
ifrom0upward with a decrementing pointer reverses every group of duplicates — the sort still produces a sorted multiset but is no longer stable. Right-to-left is not optional. - Using
count[v]directly as the slot. After the prefix sweepcount[v]is one past the last slot. You must place atcount[v] - 1, then decrement. Forgetting the- 1writes out of bounds or overwrites the neighbor bucket. - Sizing the count array to
maxinstead ofmax + 1. Valuemaxneeds its own index, so the array length ismax + 1. Off-by-one here throws on the largest key. - Re-emitting values instead of moving elements. The naive
out.push(v)version is fine for bare integers but silently drops satellite data. If the whole point is stability over records, you must copyarr[i]into the slot. - Assuming negative inputs work. Value-indexing needs non-negative keys. Negatives require an offset (
v - min) or a different approach.
Where this pattern shows up next
The prefix-sum-as-pointer trick is the engine behind the fastest sorts for bounded keys:
- Counting Sort — the plain frequency-tally version this one upgrades for stability.
- Counting Sort - Stable - Code — the same three passes viewed line by line, focused on the implementation details.
- Radix Sort — runs stable counting sort digit by digit; stability is what makes multi-pass digit sorting correct.
- Quick Sort — the comparison-based O(n log n) contrast that counting sort escapes when keys are small.
You can also step through stable counting sort interactively to watch the count array shift meaning from frequencies to pointers, then drain as elements drop into place.
FAQ
Why does counting sort scan the input right to left?
Because equal keys fill their output block from the back forward. After the prefix sum, count[v] - 1 is the last slot reserved for value v, and each placement decrements the pointer so the next v lands one slot to the left. Scanning the input right to left means the later duplicate is placed first, into the rightmost slot, and earlier duplicates fill leftward — preserving original order. A left-to-right scan reverses each duplicate group and breaks stability.
What do the prefix sums actually represent?
After the sweep, count[v] holds the number of elements less than or equal to v, which equals the count of output positions occupied by everything up to v. That makes count[v] the index one past the last home of value v, so count[v] - 1 is a concrete destination slot. The prefix sum is what converts a frequency histogram into an addressing scheme that routes each element to an exact position.
Is stable counting sort faster than quicksort?
For the right inputs, yes. Counting sort runs in O(n + k) with no comparisons, while quicksort averages O(n log n). When the key range k is comparable to n — small bounded integers like ages, scores, or digits — counting sort wins outright. When keys span a huge range, the length-k count array makes it slower and far more memory-hungry, and a comparison sort is the better choice.
When would I actually need the stable version instead of plain counting sort?
Whenever the elements carry data beyond the sort key. Plain counting sort that re-emits value repeated count[value] times loses everything except the key. If you are sorting records — orders by price, rows by a status code — you need to move the real elements, and you need equal keys to keep their input order. Stability is also non-negotiable inside radix sort, which chains several counting-sort passes and relies on earlier passes surviving later ones.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.