TAOCP 5.2.5 Exercise 9
Let a signed magnitude key be a $p$-tuple $(s, a_2, a_3, \dots, a_p),$ where $s \in {0,1}$ is the sign digit and $(a_2,\dots,a_p)$ is the magnitude expressed in radix $M$.
Section 5.2.5: Sorting by Distribution
Exercise 9. [20] [20] Continuing exercise 8, what changes should be made to the algorithms when the keys are numbers expressed in signed magnitude notation?
Verified: yes
Solve time: 1m51s
Solution
Let a signed magnitude key be a $p$-tuple
$(s, a_2, a_3, \dots, a_p),$
where $s \in {0,1}$ is the sign digit and $(a_2,\dots,a_p)$ is the magnitude expressed in radix $M$.
In signed magnitude order, all keys with $s=1$ precede all keys with $s=0$, and within each sign class the ordering of magnitudes is determined by the numeric value $a_2 M^{p-2} + \cdots + a_p$, with positive numbers in increasing magnitude order and negative numbers in decreasing magnitude order.
Algorithm R performs a stable least-significant-digit radix sort. To adapt it, two structural modifications are required so that both the global sign ordering and the reversed ordering of negative magnitudes are respected.
The first modification concerns the most significant digit. In the final pass $k=1$, step R3 extracts the sign digit $s$. To force all negative records to precede all positive records after the final concatenation in Algorithm H, the pile index must be inverted at this stage. Instead of setting $i \leftarrow s$, step R3 is replaced, for $k=1$, by
$i \leftarrow 1 - s.$
Then all records with $s=1$ are placed into pile $0$, and all records with $s=0$ are placed into pile $1$. Since Algorithm H concatenates piles in increasing index order, all negative records precede all positive records.
The second modification concerns the ordering within each sign class. The LSD method sorts digits in increasing order, which yields increasing magnitude order. This is correct for $s=0$ but incorrect for $s=1$, where decreasing magnitude order is required.
To correct this, each negative magnitude must be transformed before sorting. For every record with sign $s=1$, replace each magnitude digit $a_j$ for $2 \le j \le p$ by its radix complement
$a_j' = (M-1) - a_j.$
This transformation reverses the lexicographic order of magnitude tuples, since for two digits $x<y$ we obtain $M-1-x > M-1-y$. After this replacement, standard LSD radix ordering produces increasing order in the transformed magnitude, which corresponds to decreasing order in the original magnitude for negative numbers.
For positive records, no transformation is applied, since their required order coincides with standard lexicographic order.
Under these two changes, Algorithm R is executed without further structural alteration. The link manipulation in steps R4 and the concatenation procedure in Algorithm H remain unchanged. After completion, the resulting linked list satisfies signed magnitude order: all negative keys appear first in decreasing magnitude, followed by all positive keys in increasing magnitude.
This completes the solution. ∎