In counting sort's output pass, why is the input scanned right-to-left rather than left-to-right?

## What stability means here A sort is **stable** if records with equal keys appear in the output in the same relative order they had in the input. It is a promise about **equal** keys only — it says nothing about the ordering of distinct keys, which every correct sort gets right anyway. The setting that makes it matter: an image pipeline produces one record per detected region, already emitted in scan order (top-left to bottom-right), and a later stage groups them by an 8-bit average-luminance band. Within a band, downstream code assumes the regions are still in scan order. A stable sort keeps that promise for free; an unstable one quietly breaks it, and the failure surfaces far away as "the overlay draws regions in a jumbled order", not as a sorting bug. ## Why the direction is load-bearing After the prefix-sum pass, `count[v]` is the number of keys `<= v`. Read as an address, that is the **exclusive end** of value `v`'s block: the block occupies `[count[v-1], count[v])`. The placement loop therefore pre-decrements before writing, so the first record of key `v` that it places lands in the *last* slot of the block, the next one in the second-to-last, and so on: **the block fills backwards**. If a block fills backwards, the records must be fed to it backwards for their original order to survive. Hence the loop: ``` for i in length(a)-1 down to 0: v = key(a[i]) count[v] = count[v] - 1 out[count[v]] = a[i] ``` The last input record with key `v` is seen first and takes the block's last slot; the first input record with key `v` is seen last and takes the block's first slot. Relative order preserved. ## What a forward loop actually does Change only the direction, keeping the same counters and the same pre-decrement, and the result is still **sorted**: every record still lands inside the block belonging to its key, so nothing is misordered by key. But within each block the fill order is reversed relative to the input, so equal keys come out backwards. This is the failure a reviewer must be able to spot, because tests that only assert "the output is non-decreasing by key" pass happily. The bug is invisible to the obvious assertion and visible only to a test that checks a secondary ordering — which is the test worth writing. ## The other stable form Stability is not a property of "backwards" as such. Store the complementary convention — `start[v]` = number of keys strictly **less than** `v`, i.e. the block's inclusive start — and then a forward loop with post-increment is stable: place `a[i]` at `start[v]`, then `start[v] += 1`. First equal record gets the first slot. Both forms are stable; the mismatched pairings (exclusive end + forward, or exclusive start + backward) are the unstable ones. So the honest answer to "is counting sort stable?" is: *this* implementation is, and here is the invariant that makes it so. Reciting "counting sort is stable" without being able to point at the line that makes it true is the weak answer interviewers are probing for. There is a third variant worth separating out: the in-place version that skips placement entirely and re-emits each key value `count[v]` times over the input. People call it stable, but the label is vacuous — it only works when records are bare keys, and equal bare keys are indistinguishable, so no observable order can be preserved or destroyed. Stability is meaningful exactly when equal keys carry distinguishable payloads. ## Cost of the guarantee None, in asymptotic terms. Both stable forms are the same three passes, O(n + k) time and O(n + k) space. Stability here is bought purely by getting an index convention and a loop direction to agree — which is why it is a review question rather than a design tradeoff. What it does cost is the separate output buffer: you cannot permute records into place within the input array and keep the guarantee without extra bookkeeping, so the n-sized output array is part of the price. ## How to review it Three checks, in order. Does the counters array hold ends or starts after accumulation? Does the placement loop pre-decrement or post-increment? Does it run forward or backward? Ends pair with pre-decrement and a backward scan; starts pair with post-increment and a forward scan. Any other combination is either unstable or out of bounds — and a test that sorts records carrying a secondary sequence number, then asserts that sequence numbers within each key group are ascending, catches all of them.