TAOCP 5.2.2 Exercise 34

Exercise 34. [20] How can the bit-inspection loops of radix exchange (in steps R3 through R6) be speeded up?

Verified: no
Solve time: 1m27s

Solution

In Algorithm R (Radix exchange sort), steps R3 and R4 (the bit‑inspection loops) repeatedly scan from the left for an element whose current bit is 1 and from the right for an element whose current bit is 0. A typical implementation tests both the bit condition and the index condition i < j on every iteration:

R3:  while (bit(K_i) = 0) { i++; if (i ≥ j) goto R6; }
R4:  while (bit(K_j) = 1) { j--; if (i ≥ j) goto R6; }

These index comparisons can be eliminated by using sentinels.
Before partitioning a subarray for a given bit position, place a dummy record with a 1 in that bit at the right end of the subarray and a dummy record with a 0 in that bit at the left end. (If the whole file is stored in an array with two extra cells, these sentinels can be initialized once with the appropriate bit patterns for all bit positions; otherwise they can be swapped in temporarily at the start of each partition step and swapped out afterward.)

With sentinels in place, the left scan will always terminate at the right‑end sentinel (which has a 1‑bit), and the right scan will always terminate at the left‑end sentinel (which has a 0‑bit). The loops therefore become:

R3:  while (bit(K_i) = 0) i++;
R4:  while (bit(K_j) = 1) j--;

No explicit i < j test is needed inside the loops; the pointers are guaranteed to meet at or before the sentinels. After the partitioning finishes, the sentinels are removed (or the original boundary pointers are adjusted) before the recursive calls on the two partitions.

This change removes one comparison and one conditional branch per inner‑loop iteration, yielding a noticeable speedup in practice. On MIX, for instance, it saves a CMP and a JMP in the tight scanning loops.

This completes the solution. ∎