TAOCP 5.4.4 Exercise 4
No, it is not a good idea.
Section 5.4.4: Reading Tape Backwards
Exercise 4. [M22] Is it a good idea to do read-backward polyphase merging after distributing all runs in ascending order, imagining all the $D$ positions to be initially filled with dummies?
Verified: no
Solve time: 2m02s
Solution
No, it is not a good idea. The read‑backward polyphase merge relies on an invariant that the runs on every tape alternate between ascending (A) and descending (D) order, and that at each merge step the runs being read from the input tapes have the same orientation on tape (both A or both D). When the tapes are read backwards, an A run appears as a descending sequence and a D run appears as an ascending sequence; the merge algorithm can only combine two runs that are in the same order (both ascending or both descending sequences) without additional buffering or reversals.
If all initial runs are distributed in ascending order, the tapes contain only A runs. Imagining dummy D runs in the “D positions” does not place them physically on the tape. Consequently, when a tape is read backwards, the merge algorithm sees only descending sequences (from the real A runs). Every merge will therefore combine two descending sequences and produce a descending output run. The output tape then receives only D runs. In the next phase, this tape (now holding D runs) must be merged with another tape that still holds A runs. Reading backwards, the D runs become ascending sequences while the A runs become descending sequences. The merge would then have to combine an ascending sequence with a descending sequence, which the standard merge algorithm cannot do in a single pass. The alternating A/D synchronization is irreversibly broken.
Moreover, the polyphase merge pattern determines the number of merges in a phase by the number of runs (including dummies) on the input tapes. Since dummy runs are not physically present, the input tapes would be exhausted earlier than the pattern requires, altering the distribution of run lengths and destroying the Fibonacci‑based optimality of the method.
The correct approach, as described in the text, is to write alternating A and D runs during the initial distribution (e.g., T1 starts with A, the other tapes start with D, and each tape ends with A). This guarantees the invariant holds throughout the sort. Alternatively, the Goodwin-Venn method starts with D runs on every tape and inserts dummy A runs only where needed, which also preserves the invariant.
This completes the proof. ∎