Stable Counting Sort in Code: Prefix Sums and Right-to-Left Placement
A line-by-line walkthrough of stable counting sort in JavaScript — the count array, prefix sums, and the right-to-left placement that keeps equal keys in order.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Plain counting sort figures out how many of each value there are, then rebuilds the array from those tallies. That works, but it throws away one thing interviewers care about: which equal element came first. Stable counting sort fixes that with two small additions — turning the count array into prefix sums, and walking the input backwards when placing.
Get those two moves right and you have the exact algorithm that powers Radix Sort, where stability is not a nice-to-have but the entire reason the multi-pass digit sort produces a correct result.
This is the code-level companion to the intuition. Here we trace every line and every local variable, the way the visualizer does.
The problem
Given an array of non-negative integers, return a new array with the same values sorted in ascending order — and among equal values, preserve their original left-to-right order. That last clause is what "stable" means.
Input: arr = [4, 2, 2, 1]
Output: [1, 2, 2, 4]The values here are plain numbers, so two equal 2s look identical in the output. Stability still matters: if these were records keyed by an integer (say, players tied on score, or digits inside a larger number during a radix pass), the copy that started earlier must still end up earlier. Track the two 2s at original indices 1 and 2 — call them 2a and 2b — and a correct stable sort must emit 2a before 2b.
The brute force baseline
You could reach for a comparison sort and tell it not to reorder equal keys.
function stableSortBaseline(arr) {
return arr
.map((value, index) => ({ value, index }))
.sort((a, b) => a.value - b.value || a.index - b.index)
.map((pair) => pair.value);
}Tagging each element with its original index and breaking ties on that index gives a stable result. But it costs O(n log n) time from the comparison sort, plus O(n) space for the index tags. When the values are small integers, that comparison-based ceiling is wasteful — you can do it in linear time by counting instead of comparing.
The key insight: prefix sums are end-pointers
Counting sort's core trick is that if you know how many elements are less than or equal to a value v, you know exactly where the vs end in the output.
Build a frequency array count, where count[v] is how many times v appears. Then run a prefix sum over it left to right, so each count[v] becomes the count of elements ≤ v. After that transform, count[v] is the position just past the last slot where a v belongs — an exclusive end-pointer into the output.
Now place elements by scanning the input right to left. For each value, read its end-pointer, drop the value one slot before it (sortedArr[count[v] - 1]), then decrement the pointer so the next equal value lands one slot earlier. Walking backwards means the last equal element gets the highest slot and the first equal element gets the lowest — original order preserved. That right-to-left direction is the whole stability guarantee. The Counting Sort - Stable - Logic post proves why that ordering holds.
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;
}The count array does double duty. In the first loop it holds raw frequencies. The prefix-sum loop then rewrites those same slots into cumulative counts — no second array needed. The placement loop reads x = count[arr[i]] as the exclusive end position, writes at x - 1, and decrements so the next identical value slides one slot down. Everything hinges on that final loop counting down from arr.length - 1.
Walkthrough
Trace arr = [4, 2, 2, 1]. Max is 4, so count has 5 slots (indices 0 through 4).
Count phase — one bump per element:
| Read value | count after |
|---|---|
| 4 | [0, 0, 0, 0, 1] |
| 2 | [0, 0, 1, 0, 1] |
| 2 | [0, 0, 2, 0, 1] |
| 1 | [0, 1, 2, 0, 1] |
Prefix-sum phase — each slot absorbs the one to its left:
| i | count[i] = count[i] + count[i-1] | count after |
|---|---|---|
| 1 | 1 + 0 = 1 | [0, 1, 2, 0, 1] |
| 2 | 2 + 1 = 3 | [0, 1, 3, 0, 1] |
| 3 | 0 + 3 = 3 | [0, 1, 3, 3, 1] |
| 4 | 1 + 3 = 4 | [0, 1, 3, 3, 4] |
Now count[2] = 3 means "three elements are ≤ 2", so the last 2 belongs at index 3 - 1 = 2.
Placement phase — scan right to left, write at x - 1, then decrement:
| i | arr[i] | x = count[arr[i]] | write sortedArr[x-1] | count[arr[i]] after | sortedArr |
|---|---|---|---|---|---|
| 3 | 1 | 1 | [0] ← 1 | count[1] = 0 | [1, _, _, _] |
| 2 | 2 (2b) | 3 | [2] ← 2 | count[2] = 2 | [1, _, 2, _] |
| 1 | 2 (2a) | 2 | [1] ← 2 | count[2] = 1 | [1, 2, 2, _] |
| 0 | 4 | 4 | [3] ← 4 | count[4] = 3 | [1, 2, 2, 4] |
Result: [1, 2, 2, 4]. Watch the two 2s. 2b (original index 2) landed at output index 2 first; then 2a (original index 1) landed at index 1. 2a ends up before 2b — original order held, exactly because we walked the input backwards and decremented the shared pointer between them.
Complexity
Let n be the input length and k be max + 1, the size of the count array.
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n + k) | one pass to count (n), one pass over buckets for the prefix sum (k), one pass to place (n) |
| Space | O(n + k) | the count array of size k plus the sortedArr output of size n |
There is no log factor because nothing is ever compared — positions come straight from arithmetic on the counts. The catch is k: if max is huge relative to n (say sorting [0, 1000000]), the count array dwarfs the input and the "linear" cost balloons. Counting sort wins when values live in a small, dense range.
Common mistakes
- Running the prefix sum right to left. The loop must go left to right so
count[i - 1]is already a finished cumulative sum when you read it. Reversing it double-counts and corrupts every position. - Placing left to right. Scan the input from
arr.length - 1down to0. A forward scan still sorts, but it reverses the order of equal keys — you lose stability and break any radix sort built on top. - Writing at
count[v]instead ofcount[v] - 1. The prefix sum is an exclusive end-pointer (a count, not an index). Forgetting the- 1writes one slot too far right and overflows the array. - Sizing count off the length instead of the max. The array needs
max + 1buckets, notarr.length. Index it by value, never by position. - Assuming negative inputs work. This version indexes
countby value directly, so it only handles non-negative integers. Negatives need an offset (value - min).
Where this pattern shows up next
Stable counting sort is a building block, not an endpoint:
- Counting Sort - Stable - Logic — the proof of why right-to-left placement with prefix-sum end-pointers preserves order among equal keys.
- Counting Sort — the simpler count-and-rebuild version that ignores stability, useful when equal keys are truly interchangeable.
- Radix Sort — runs stable counting sort once per digit; without stability, earlier digit passes would be scrambled by later ones.
- Quick Sort — the comparison-based O(n log n) alternative for when values are not small dense integers.
You can also step through stable counting sort line by line with a live locals tracker that shows i, arr[i], and the shrinking end-pointer on every placement.
FAQ
What makes counting sort stable?
Two things working together: the prefix-summed count array gives each value an exclusive end-pointer into the output, and the placement loop scans the input from right to left. Because you place the last-seen equal element first (at the highest available slot) and decrement the shared pointer before the next equal element, earlier elements land at lower indices. Their original relative order survives. Scan forward instead, and equal keys come out reversed.
Why turn the count array into prefix sums?
Raw frequencies tell you how many of each value exist but not where they go. Running a left-to-right prefix sum rewrites count[v] into the number of elements ≤ v, which is precisely the position just past the last slot a v should occupy. That converts a histogram into direct output addresses, so placement becomes a constant-time lookup per element instead of a search.
What is the time and space complexity of stable counting sort?
Time is O(n + k) and space is O(n + k), where n is the number of elements and k is max + 1. The three passes — count, prefix sum, place — are each linear in n or k, and there are no comparisons, so no log factor appears. The trade-off is the count array's size: when the value range k is far larger than n, both time and space degrade, which is why counting sort is reserved for small, dense integer ranges.
Why does the placement loop write at count[value] - 1?
After the prefix sum, count[value] is a count of elements ≤ value, which is an exclusive upper bound — one past the last valid index for that value. Array indices are zero-based, so the actual slot is count[value] - 1. Writing at count[value] directly would place the element one position too far right and eventually index out of bounds. Decrementing count[value] after each write moves that pointer down for the next equal element.
Can stable counting sort handle negative numbers?
Not as written — it indexes the count array by the value itself, so a negative value would produce a negative index. To support negatives, find the minimum value and offset every index by -min, allocating max - min + 1 buckets. The logic is otherwise identical; you are just shifting the value range to start at zero before counting and placing.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.