Exercise 27. [23] [23] Once the initial runs have been distributed to tapes in a perfect distribution, the polyphase strategy is simply to “merge until empty”: We merge runs from all nonempty input tapes until one of them has been entirely read; then we use that tape as the next output tape, and let the previous output tape serve as an input.

Does this merge-until-empty strategy always sort, no matter how the initial runs are distributed, as long as we distribute them onto at least two tapes? (One tape will, of course, be left empty so that it can be the first output tape.)

Verified: no
Solve time: 4m56s

The reviewer’s diagnosis is correct: the previous proof implicitly replaced each tape by a globally sorted sequence, which is false. The correct resolution is not to repair that k-way merge argument, but to observe that the stated “merge until empty” procedure is not guaranteed to produce sorted output if run distribution is arbitrary, even when each run is individually sorted and there are at least two tapes.

The key issue is that the algorithm performs a record-level greedy merge across concatenated runs, but concatenation of sorted runs is not a sorted sequence. A standard k-way merge correctness argument does not apply.

1. What the algorithm actually does

At any moment, each tape contributes its current “head record”, meaning the next unread record in the current run. When a run ends, the head moves to the first record of the next run on that same tape.

Thus each tape behaves as a single stream:

$$ \text{run}_1 ;\Vert; \text{run}_2 ;\Vert; \cdots $$

where each $\text{run}_i$ is sorted internally but there is no ordering relation between runs.

The merge step always selects the minimum among current heads.

This is exactly a greedy merge of several not-necessarily-sorted streams.

2. Why the greedy argument fails

The standard correctness proof of a k-way merge requires:

Each input sequence is globally nondecreasing.

That condition fails here because a tape may contain:

$$ (3);\Vert;(1) $$

(two sorted runs concatenated).

So a later run may start with a value smaller than earlier output from that tape.

This breaks the invariant needed for correctness of greedy merging.

3. Concrete counterexample

We now construct a full execution where the algorithm produces a non-sorted output.

Assume two tapes $T_1, T_2$.

Initial distribution

Tape $T_1$: runs $[3]$, $[1]$
Tape $T_2$: run $[2]$
Tape $T_3$: empty (allowed, since at least two tapes must be used)

Each run is individually sorted.

So we have:

$$ T_1: 3 \mid 1,\quad T_2: 2,\quad T_3: \emptyset $$

Step-by-step merge

Initial heads:

$T_1: 3$
$T_2: 2$

Output $\min(3,2)=2$.

Output: $2$ 2. Advance $T_2$ (now empty), so only $T_1$ remains active in this phase. 3. Output from $T_1$: $3$ (end of first run)

Output so far:

$$ 2,,3 $$

Now $T_1$ advances into next run, whose first element is $1$.
Next output is $1$.

Final output:

$$ 2,,3,,1 $$

This is not sorted.

4. Why this violates no rules of the algorithm

Nothing in the problem statement forbids:

a later run on a tape containing smaller keys than earlier runs,
arbitrary interleaving of key distributions across tapes.

The only requirement is that each run is internally sorted.

Thus the above configuration is valid.

5. Structural reason for failure

The algorithm relies on a hidden assumption:

Each tape behaves like a sorted stream during merging.

That assumption is false because run boundaries introduce decreases:

$$ \max(\text{run}i) \not\le \min(\text{run}{i+1}) $$

So the greedy selection step can irrevocably output a large element from one tape before a smaller element appears later on the same tape.

6. Conclusion

No, the merge-until-empty strategy does not always produce a sorted output when runs are arbitrarily distributed across at least two tapes.

The failure arises because the algorithm performs a k-way merge over sequences that are only piecewise sorted, not globally sorted, and greedy merging is not valid under that condition.

$$ \boxed{\text{The strategy is not correct in general; it admits counterexamples.}} $$

TAOCP 5.4.2 Exercise 27