= Radix sort key encoding
An encoding for <radix sort> must make the intended <total order> of <sort keys> agree with the <lexicographic order> of its fixed-width <numerical digit> <tuples>. The <positional notation> for bounded nonnegative <integers> has this property. At the most significant differing position $m$, a one-unit <numerical digit> difference contributes $R^m$, while all lower positions together contribute at most
$$
(R-1)\sum_{j=0}^{m-1}R^j=R^m-1.
$$
This <geometric series> shows why lower <numerical digits> cannot reverse that comparison. Leading zero padding works here because it preserves <place values> and the represented <integer>.
For signed <integers> in a known <integer interval> $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This <order-preserving function> is also <injective>: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le7$, the four-<bit> encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed <sort keys> when displaying the complete <sorting records>; the encoding need not replace their data. Sorting the unsigned values of raw <two's complement> <bit> patterns would put nonnegative <integers> before negative ones, so their representation alone is not this ordered encoding.
For variable-length <strings>, first specify the <alphabet> order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every <string> have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The <strings> $\varepsilon,a,aa,ab,b$ encode as $000,100,110,120,200$ in <radix> three, which preserves their <lexicographic order>. A differing real symbol decides the comparison; at a prefix boundary, the shorter <string>'s zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw <bytes> with zero also fails if zero is an allowed data symbol: distinct <strings> can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.
\Image[/radix-sort-stability-and-key-encoding.png]
{title=Stable ties preserve lower digits; suitable encodings preserve the intended order}
{description=Original counterexample above: reversing a tens tie destroys the units order and a later stable hundreds pass cannot repair it. Below: signed <integer> offsets and a reserved end marker for bounded <strings> produce increasing fixed-width encodings. All entries are exact constructed examples.}
Back to article page
