 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 mostThis 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\le 7$, 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 $\epsilon ,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.