TAOCP 5.4.4 Exercise 5

Section 5.4.4: Reading Tape Backwards

Exercise 5. ▶ [23] What formulas for the strings of merge numbers replace (8), (9), (10), and (11) of Section 5.4.2, when read-backward polyphase merging is used? Show the

merge numbers for the fifth level distribution on six tapes, by drawing a diagram like Fig. 71(a).

Verified: no
Solve time: 10m24s

Solution

Formulas for the strings of merge numbers

In standard polyphase merging (Section 5.4.2) the merge numbers are the Fibonacci numbers of order (T-1).
Let (F_n^{(T-1)}) denote these numbers, defined by
[ F_0^{(T-1)}=1,\quad F_n^{(T-1)}=0;(n<0),\quad F_n^{(T-1)}=\sum_{i=1}^{T-1}F_{n-i}^{(T-1)};(n>0). ]

Equations (8)-(11) of Section 5.4.2 give the merge numbers for the four tapes that are not the final output tape (or, equivalently, the recurrences satisfied by the columns of the merge‑number table).
For read‑backward polyphase merging the merge pattern is unchanged, but the initial distribution must be taken from the levels where tape 1 is the final output tape and the initially empty tape is not tape 1. As stated in the text, these are exactly the levels whose numbers are not congruent to (1) modulo (T). If we list the admissible levels in increasing order as
[ n_0=0,; n_1=2,; n_2=3,; \dots,; n_k = k+\bigl\lfloor\frac{k-1}{T-1}\bigr\rfloor\quad(k\ge 1), ] then the merge numbers for tape (j) at the (k)-th admissible level are the standard merge numbers evaluated at level (n_k). Hence the strings of merge numbers that replace (8)-(11) are simply the subsequences of the standard polyphase strings obtained by deleting the entries whose level index is (\equiv 1\pmod{T}). In other words, if the standard merge numbers for tape (j) are (a_n^{(j)}), then the read‑backward strings are (a_{n_k}^{(j)}).

Merge numbers for the fifth‑level distribution on six tapes

The fifth‑level distribution in Table (1) (which corresponds to standard level 5) is

(Tape 6 is the initially empty tape.) The final output must appear on T1. Simulating the polyphase merge (each phase merges the 5 non‑empty tapes onto the empty one, the number of merges being the minimum run count among the inputs) yields the following phases.

This table is the diagram analogous to Fig. 71(a) for the fifth‑level distribution on six tapes. The “Merges” column records how many runs are merged in each phase (the minimum of the input tape counts). After Phase 5 the sorted file resides on T1 as a single ascending run.

∎