Counting sort prefix ranges ($[S_k,P_k)$)

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.