= Stable record placement in counting sort
{title2=$E_k\gets E_k-1,\quad B_{E_k}\gets A_i$}
Initialize a mutable endpoint <array> $E$ to the inclusive cumulative counts $P$. Scan <input> <array indices> $i=n-1,n-2,\ldots,0$. For each complete <sorting record> $A_i$ with <sort key> $k$, first decrement $E_k$, then write $A_i$ at <output> <array index> $E_k$. This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.<Open Data Structures: An Introduction by Pat Morin/11.2 Counting Sort and Radix Sort>[Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, final scan paragraph and stability paragraph after Theorem 11.7]{ref}
In the worked example, the first <input> <sorting record> read is $(2,\mathrm G)$ at <array index> six. Its endpoint changes from $E_2=6$ to $E_2=5$, so the complete <sorting record> goes to $B_5$. Next, $(3,\mathrm F)$ changes $E_3$ from seven to six and goes to $B_6$. Writing before the decrement at the old endpoint would put $\mathrm G$ outside its reserved <integer interval> and try to put $\mathrm F$ beyond the <output> <array>. All seven writes are:
$$
\begin{array}{c|c|c|c|c}
\text{step}&\text{input index }i&A_i& E_k\text{ before}\to\text{after}&\text{output index}\\\hline
1&6&(2,\mathrm G)&6\to5&5\\
2&5&(3,\mathrm F)&7\to6&6\\
3&4&(0,\mathrm E)&2\to1&1\\
4&3&(1,\mathrm D)&3\to2&2\\
5&2&(2,\mathrm C)&5\to4&4\\
6&1&(0,\mathrm B)&1\to0&0\\
7&0&(2,\mathrm A)&4\to3&3
\end{array}
$$
Each endpoint changes only when a <sorting record> with its own <sort key> is placed. Consequently, $E_2$ stays at five through the placements of $\mathrm F,\mathrm E,\mathrm D$ before dropping to four for $\mathrm C$.
\Image[/counting-sort-reverse-stable-placement.png]
{title=A backward <input> scan gives forward order among equal <sort keys>}
{description=Original complete trace of the seven-<sorting record> example. Each row shows the endpoint decrement and resulting <output> <array>; the newly written complete <sorting record> is dark. Both <input> and <output> <array indices> start at zero. The final order is $\mathrm B,\mathrm E,\mathrm D,\mathrm A,\mathrm C,\mathrm G,\mathrm F$.}
Here is a complete implementation under the stated <input> contract; each <sorting record> is a pair whose first component is its <integer> <sort key>:
``
def counting_sort_records(records, K):
end = [0] * K
output = [None] * len(records)
for key, data in records:
end[key] += 1
for key in range(1, K):
end[key] += end[key - 1]
for i in range(len(records) - 1, -1, -1):
key = records[i][0]
end[key] -= 1
output[end[key]] = records[i]
return output
``
The same <array> `end` successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas $c,S,P$ describe their mathematical values without requiring three stored <arrays>. The write copies the complete <sorting record>, including its associated data. In particular, two occurrences of an identical pair still cause two separate writes.
For a short <algorithm correctness> proof, let $r_k$ be the number of already placed <sorting records> with <sort key> $k$. A <loop invariant> is
$$
E_k=P_k-r_k,\qquad [S_k,E_k)\text{ is unfilled},\qquad [E_k,P_k)\text{ is filled}.
$$
All <integer intervals> here mean <output> <array indices>. Initially $r_k=0$, so each whole reserved <integer interval> is unfilled. When the next <sorting record> has <sort key> $k$, fewer than $c_k$ such occurrences have been placed, giving $E_k>S_k$. Decrementing selects a fresh slot inside its reserved <integer interval>. At termination, $r_k=c_k$ and $E_k=S_k$: every <output> slot has been filled exactly once with a complete <input> occurrence. The disjoint, increasing <sort key> ranges establish <sortedness>, while the fresh-slot property establishes <sorting permutation preservation>.
For <stable sorting>, take two <input> occurrences with equal <sort keys> at <array indices> $i<j$. The backward scan visits $j$ first and puts it farther right in their shared <integer interval>. When $i$ is visited, the endpoint has decreased at least once, so its <output> position is smaller. Thus their original order survives. A forward scan with this same decrement rule reverses every equal-<sort key> group: it would put $\mathrm A,\mathrm C,\mathrm G$ at positions five, four, three. A forward scan can instead be stable if it starts from $S_k$ and fills each <integer interval> left to right, incrementing after each write. The scan direction and endpoint convention must agree.
Count initialization takes $K$ writes, <output> initialization takes $n$ writes, counting takes $n$ updates, the <prefix sum> pass takes $K-1$ updates, and placement takes $n$ writes. Hence <time complexity> and auxiliary storage are $O(n+K)$ in <Big O notation>, assuming constant-cost <sort key> access, <integer> arithmetic, <array> indexing and complete <sorting record> movement. Large records can instead be represented by constant-size references.<Open Data Structures: An Introduction by Pat Morin/11.2 Counting Sort and Radix Sort>[Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, auxiliary counter and output arrays, loop-cost discussion and Theorem 11.7]{ref}
For example, three <sorting records> with <sort keys> zero, $999999$ and zero require one million counters if $K=1000000$; unused <sort keys> still incur initialization and <prefix sum> work. The bound is therefore linear in the <input> length only when $K=O(n)$. Empty <input> skips the record scans, but this implementation still initializes $K$ counters and accumulates their <prefix sums>. For nonempty <input>, counting all $n$ records and filling their ranges gives a concrete termination argument.
Direct <sort key> indexing is a different operation from a binary comparison. The <comparison sorting lower bound> concerns <comparison sorts>; <counting sort> uses its restricted <integer> <sort keys> as <array indices>. Its small-$K$ speed is particularly useful for categorical numerical labels and for each <stable sorting> pass of <radix sort>: the reserved <integer intervals> turn group sizes into exact destinations.
Back to article page
