TAOCP 5.4.2 Exercise 2

Section 5.4.2: The Polyphase Merge

Exercise 2. [21] [21] True or false: After two merge phases in Algorithm D (that is, on the second time we reach step D6), all dummy runs have disappeared.

Verified: no
Solve time: 4m28s

The previous solution failed because it replaced Algorithm D with an unproved “Fibonacci level” abstraction and then reasoned about dummy runs in that model. We restart from the actual mechanism of Algorithm D in §5.4.2.

Correct analysis

In Algorithm D (polyphase merging), a dummy run is an artificial run used only to complete the initial distribution of runs across tapes so that the Fibonacci-like invariant of the tape configuration is satisfied.

Crucially, a dummy run is not a special object that “automatically disappears” after a fixed number of merge phases. It disappears only when it is actually involved in a merge in which it is absorbed by a real run.

The key operational rules are:

A merge step takes the front runs of two input tapes.
If both inputs are real, the output is real.
If one input is a dummy run and the other is real, the result is the real run (the dummy is eliminated).
If both inputs are dummy runs, the result is a dummy run.
Therefore, dummy runs persist unless they are paired with real runs during a merge.

Thus, the disappearance of dummy runs depends entirely on whether the merge schedule forces every dummy run to be paired with a real run within the given number of phases.

Structure of a merge phase

One merge phase (one execution of step D6 repeated until exhaustion of one tape) only guarantees:

All runs currently designated for merging in that phase are processed.
The distribution of runs is updated according to the tape rotation rule of polyphase merging.

However, nothing in the definition of a phase implies that:

every tape participates equally in eliminating dummy runs, or
every dummy run is forced to meet a real run within two phases.

In particular, dummy runs can remain isolated on a tape that is not yet “aligned” with a tape containing real runs during the first few phases.

Key obstruction

Initially, dummy runs are concentrated on specific tapes as part of the completion of the Fibonacci-based distribution. During early phases:

merges are driven by the current empty-output tape,
only selected pairs of tapes are active,
and not all tape pairs are forced to interact.

Hence, it is entirely possible for dummy runs to remain on a tape that does not interact with real runs during the first two merge phases.

Since a dummy run disappears only when it is actually merged with a real run, such dummy runs persist.

Counterexample (structural)

Take any valid polyphase setup with $T \ge 3$ where the initial distribution requires at least one nonzero block of dummy runs on a tape that is not scheduled to merge directly with the dominant real-run tapes in the first two phases.

For instance:

all real runs are distributed among two tapes,
all dummy runs are placed on a third tape (as required by the initial completion rule),
the first merge phase combines only the real-run tapes,
the second phase still does not force merges involving the dummy-only tape with a real-run tape.

After two phases:

at least one dummy run remains untouched,
hence at least one dummy run still exists.

This configuration is consistent with the rules of Algorithm D, since the tape schedule is determined by the polyphase ordering, not by any requirement that dummy runs must be immediately consumed.

Conclusion

The earlier argument failed because it assumed a global “level decrease” model that does not exist in Algorithm D. The correct analysis shows that dummy runs are eliminated only through actual participation in merges with real runs, and the algorithm does not guarantee that all dummy runs are consumed within two merge phases.

Therefore, there exist valid inputs and initial distributions for which dummy runs persist after two merge phases.

Final answer: False.