= Counting sort prefix ranges
{title2=$[S_k,P_k)$}
For $n\geq0$ <sorting records> with <integer> <sort keys> in $\{0,\ldots,K-1\}$, where $K\geq1$, let $c_k$ count the <input> occurrences of <sort key> $k$. Define two <prefix sums>:
$$
S_k=\sum_{h=0}^{k-1}c_h,\qquad P_k=\sum_{h=0}^{k}c_h=S_k+c_k.
$$
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 interval>
$$
\{j\in\mathbb Z:S_k\leq j<P_k\}=[S_k,P_k)\cap\mathbb Z.
$$
Its right endpoint $P_k$ is excluded: the last occupied <array index> is $P_k-1$ when $c_k>0$.<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, paragraphs after Figure 11.7: running sums count keys at most k and determine the output block]{ref}
For the seven-<sorting record> example, the frequency <array>, inclusive cumulative count <array>, and start <array> are
$$
c=(2,1,3,1),\qquad P=(2,3,6,7),\qquad S=(0,2,3,6).
$$
Thus <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.
\Image[/counting-sort-frequency-prefix-ranges.png]
{title=Frequencies and <prefix sums> reserve disjoint <counting sort> output ranges}
{description=Original seven-<sorting record> example with $K=4$. The bar heights count <sorting records>. The table gives the start $S_k$ and exclusive endpoint $P_k$ for each <sort key>; the lower strip shows zero-based <output> <array indices>. The boundary seven lies just beyond the last slot six.}
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.
Back to article page
