TAOCP 5.4.4 Exercise 11

Section 5.4.4: Reading Tape Backwards

Exercise 11. ▶ [20] True or false: Any read-backward merge pattern that uses nothing but $(T-1)$-way merging must always have the runs alternating $ADAD \ldots$ on each tape; it will not work if two adjacent runs appear in the same order.

Verified: no
Solve time: 10m09s

Solution

False. The statement claims that in any read‑backward merge pattern using only ((T-1))-way merges, the runs on every tape must strictly alternate between ascending ((A)) and descending ((D)) order, and that the pattern fails if two adjacent runs ever have the same orientation. This is not true.

The text describes an alternative distribution method due to Goodwin and Venn [CACM 7 (1964), 315] for read‑backward polyphase merging. In this method the initial distribution is built by starting with a (D) run on each tape and then adding dummy runs as needed. The text explicitly states:

“Other dummies are imagined at the end of the tapes, or grouped into pairs in the middle.”

When dummy runs are grouped into pairs, two dummy runs of the same orientation (both (A) or both (D)) become adjacent on a tape. This violates the strict (ADAD\ldots) alternation, yet the merge pattern still works correctly,the dummy runs are merged instantly because they have zero length, and the overall polyphase merge proceeds without error. The placement of such dummy pairs is analyzed in Exercise 5.4.4-5.

Thus a valid ((T-1))-way read‑backward merge pattern (the Goodwin-Venn polyphase distribution) exists in which adjacent runs on a tape have the same order, disproving the claim.

∎