Counting sort ($T(n,K)=O(n+K)$)

Counting sort uses integer sort keys in $\{0,\dots ,K-1\}$ directly as indices into an array of counts. Constant-cost counting and indexing give $O(n+K)$ time complexity in Big O notation. To retain complete sorting records, cumulative counts locate their output ranges; filling each range from its end while scanning the input backwards gives stable sorting. Emitting bare sort keys from counts would discard associated data. The $K$ term matters when the key range is large.^[ref]

For an original worked example, take $n=7$ complete sorting records and $K=4$ possible integer sort keys:The letters label the associated data, and are never compared. Both input and output array indices start at zero, so their valid positions are $0,\dots ,6$; the count array has array indices $0,\dots ,3$. Stable sorting must produceThe equal-sort key groups retain $\mathrm{B},\mathrm{E}$ and $\mathrm{A},\mathrm{C},\mathrm{G}$ in arrival order. Counting sort prefix ranges explain where those groups belong; stable record placement in counting sort explains how to fill them without losing that order or the complete sorting records.

For $n\ge 0$ sorting records with integer sort keys in $\{0,\dots ,K-1\}$, where $K\ge 1$, let $c_k$ count the input occurrences of sort key $k$. Define two prefix sums:The empty sum gives $S_0=0$. Here $c_k,S_k,P_k$ are counts of sorting records. Exactly $S_k$ sorting records have smaller sort keys, so the output positions for sort key $k$ form the half-open integer intervalIts right endpoint $P_k$ is excluded: the last occupied array index is $P_k-1$ when $c_k>0$.^[ref]

For the seven-sorting record example, the frequency array, inclusive cumulative count array, and start array areThus sort keys zero, one, two and three occupy the integer intervals $[0,2)$, $[2,3)$, $[3,6)$ and $[6,7)$, respectively. In particular, the three sorting records with sort key two belong at array indices three, four and five. The inclusive cumulative count $P_2=6$ counts all six sorting records with sort keys at most two; six is the exclusive endpoint, not the final position of a sorting record with sort key two.

These integer intervals fit together because $P_k=S_{k+1}$ for $k<K-1$, and $P_{K-1}=n$. Their lengths $P_k-S_k=c_k$ add to $n$, so they partition all output positions without overlaps or gaps. An absent sort key contributes an empty integer interval: with frequencies $(0,2,0,1)$, the endpoints are $(0,2,2,3)$ and sort key two has range $[2,2)$. For empty input, every count and endpoint is zero; every reserved integer interval is empty. This makes the same formulas cover missing sort keys and the empty case.

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.