TAOCP 5.2.5 Exercise 8

Let the radix be $M$ and let keys be written as $(a_1,a_2,\dots,a_p)$ with digits $0 \le a_i < M$.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.5: Sorting by Distribution

Exercise 8. [20] [20] The radix-sorting algorithms discussed in the text assume that all keys being sorted are nonnegative. What changes should be made to the algorithms when the keys are numbers expressed in two’s complement or ones’ complement notation?

Verified: yes
Solve time: 1m50s

Solution

Let the radix be $M$ and let keys be written as $(a_1,a_2,\dots,a_p)$ with digits $0 \le a_i < M$. In Algorithm R the ordering of records after completion is determined lexicographically by the sequence of bucket indices used in the passes, and the final pass ($k=p$) determines the most significant comparison.

For nonnegative keys, lexicographic order agrees with the natural numerical order because each digit is interpreted as an unsigned base-$M$ coefficient.

For signed representations in either two’s complement or ones’ complement, the difficulty is that the most significant digit $a_1$ no longer represents an unsigned contribution to the value. The lower digits $a_2,\dots,a_p$ remain unchanged in their ordering role, so only the extraction rule in step R3 for $k=p$ and the final interpretation of the most significant digit require modification.

Two’s complement

In $M$-ary two’s complement, the most significant digit contributes a negative weight. Writing the numeric value in the standard form,

$a_1 M^{p-1} + a_2 M^{p-2} + \cdots + a_p,$

is replaced conceptually by a signed interpretation in which the range $a_1 \in [0,M-1]$ is split into negative and nonnegative halves. The correct total order is obtained by treating the most significant digit cyclically shifted by $M/2$ so that the negative half precedes the nonnegative half.

Thus step R3 must be replaced only for the last pass $k=p$ by

$i \leftarrow (a_1 - M/2) \bmod M.$

All other passes remain unchanged. The effect is that digits $a_1 \in [M/2, M-1]$ are mapped to $0,1,\dots,M/2-1$ in increasing order of magnitude of negativity, while digits $a_1 \in [0,M/2-1]$ are mapped to $M/2,\dots,M-1$ in increasing order of positivity.

After this modification, Algorithm H concatenates piles in the order $0,1,\dots,M-1$, which yields first all negative numbers in correct order, followed by all nonnegative numbers in correct order. No further change in linking or pile processing is required.

Ones’ complement

In ones’ complement, the most significant digit again encodes sign, but two representations correspond to zero: the all-zero positive representation and the all-$ (M-1) $ negative representation. The same cyclic shift used for two’s complement,

$i \leftarrow (a_1 - M/2) \bmod M,$

preserves the ordering of all nonzero values and places the two zero representations into adjacent buckets at the boundary between negative and nonnegative ranges.

To preserve a consistent total order, the concatenation order in Algorithm H remains unchanged. The resulting list has all negative numbers first, then both representations of zero (adjacent), then all positive numbers.

No change is required in the lower-digit passes or in the linking mechanism, since ones’ complement affects only the interpretation of the most significant digit and not the stability of digitwise distribution in lower positions.

This completes the proof. ∎