 Stable record placement in counting sort

Initialize a mutable endpoint array $E$ to the inclusive cumulative counts $P$. Scan input array indices $i=n-1,n-2,\dots ,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.^[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: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}$.

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 isAll 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.^[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.