TAOCP 5.4.4 Exercise 17

Section 5.4.4: Reading Tape Backwards

Exercise 17. ▶ [28] (Richard D. Pratt.) To achieve ascending order in a read-backward cascade merge, we could insist on an even number of merging passes; this suggests a technique of initial distribution that is somewhat different from Algorithm 5.4.3C.

a) Change 5.4.3–(1) so that it shows only the perfect distributions that require an even number of merging passes.

b) Design an initial distribution scheme that interpolates between these perfect distributions. (Thus, if the number of initial runs falls between perfect distributions, it is desirable to merge some, but not all, of the runs twice, in order to reach a perfect distribution.)

Verified: no
Solve time: 7m03s

Setup

In a read‑backward cascade merge on (T) tapes, each merge pass reverses the order of the runs. If the initial runs are ascending, then after an odd number of merge passes the final output is descending; after an even number it is ascending. To obtain ascending output without an extra copy/rewind we must use a merge pattern that requires an even number of merging passes.

The perfect distributions for the ordinary (read‑forward) cascade merge are given in the table 5.4.3-(1). Each row of that table corresponds to a “level” (\ell); the number of merging passes needed to complete the sort from that distribution is exactly (\ell). The table lists the number of runs placed on each tape and the total (S_\ell).

Solution

a) Modified table of perfect distributions

We change 5.4.3-(1) by deleting every row whose level (\ell) is odd. The remaining rows are those with (\ell = 0, 2, 4, 6, \dots); they show the perfect distributions that require an even number of merging passes. For these distributions the final sorted output will appear in ascending order when the merge is performed by reading backwards.

(If the original table is written for a specific (T), the modified table simply omits the odd‑(\ell) lines. The recurrence that generates the perfect distributions is unchanged; we merely restrict attention to the even levels.)

b) Interpolation scheme for arbitrary numbers of runs

Let (S) be the number of initial runs. We construct an initial distribution that will sort in an even number of passes without using dummy runs. The idea is to work backwards from the final sorted run using the vector representation described in Section 5.4.4.

1. Choose the target even level.
   Find the smallest even (\ell) such that the perfect distribution total (S_\ell \ge S). (If (S = S_\ell) we simply use that perfect distribution.)

2. Build the merge vectors backwards.
   The perfect distribution of level (\ell) corresponds to a sequence of merge vectors [ \mathbf{y}^{(\ell)},; \mathbf{y}^{(\ell-1)},; \dots,; \mathbf{y}^{(1)},; \mathbf{y}^{(0)} ] where each (\mathbf{y}^{(i)}) has exactly one (-1) (the output tape) and the other entries are (0) or (+1) (input tapes). The sum (\mathbf{v}^{(\ell)} = \sum_{i=0}^{\ell} \mathbf{y}^{(i)}) gives the initial distribution of the perfect cascade.

   We need a distribution with total (S) instead of (S_\ell). Let (D = S_\ell - S) be the number of runs we must “remove”.

3. Replace (D) initial runs by merged runs.
   The vector (\mathbf{y}^{(\ell)}) represents the first merge step (the one closest to the initial distribution). Its (+1) components indicate the tapes that supply the initial runs. We select (D) of these (+1) entries and replace each selected (+1) by a merged run that is formed by merging two initial runs together during the distribution pass.

   Concretely, during the initial distribution we write the runs onto the tapes as follows:

   • For the (D) selected input positions, we take two initial runs, merge them into one run (this is a single preliminary merge), and write that merged run onto the corresponding tape.
   • All other initial runs are written singly as usual.

   This reduces the total number of runs from (S_\ell) to (S_\ell - D = S). The preliminary merges are performed while the tape is being written forward (the distribution pass), so they cost essentially the same as writing the runs separately.

4. Why the final order is ascending.
   The main cascade merge still consists of exactly (\ell) merge passes (the vectors (\mathbf{y}^{(\ell-1)},\dots,\mathbf{y}^{(0)})), which is an even number. Every run that was written singly undergoes exactly (\ell) merges in the cascade; because (\ell) is even, it ends ascending.
   Each merged run (result of a preliminary merge) undergoes one preliminary merge followed by the (\ell) cascade merges, i.e. (\ell+1) merges total. However, the preliminary merge is performed while reading the input forward and writing forward, so it does not reverse the order - it preserves the ascending order of the two input runs. The subsequent (\ell) read‑backward merges do reverse the order (\ell) times. Since (\ell) is even, the overall effect is ascending. (Equivalently, the preliminary merge can be regarded as part of the distribution, not as a merge pass that reverses order.)

5. Completing the sort.
   After the initial distribution, we simply execute the cascade merge pattern dictated by the vectors (\mathbf{y}^{(\ell-1)},\dots,\mathbf{y}^{(0)}). Because the distribution matches the perfect distribution except for the (D) merged runs, every merge step will find the required runs on the correct tapes; no dummy runs are needed. The final output appears on the tape specified by (\mathbf{y}^{(0)}) and is in ascending order.

This scheme interpolates smoothly between the even‑level perfect distributions: when (S) equals a perfect total (S_\ell) we use the pure cascade; when (S) falls strictly between (S_{\ell-2}) and (S_\ell) we use the level‑(\ell) pattern and merge exactly (S_\ell - S) pairs of runs during the distribution pass.

Verification

Consider (T = 4). The perfect distributions (from 5.4.3-(1)) for the first few levels are:

(Only even (\ell) are kept after the modification.)

Take (S = 5). The smallest even (\ell) with (S_\ell \ge 5) is (\ell = 4) ((S_4 = 14)). We need (D = 9) merged runs. The vector (\mathbf{y}^{(4)}) for the 14‑run perfect distribution has (+1) entries corresponding to the 14 initial runs. We replace 9 of those (+1)'s by merged runs, i.e. we merge 9 pairs of initial runs during the distribution pass. The resulting distribution has (14 - 9 = 5) runs on the tapes. The main cascade then performs 4 merge passes (an even number). The 5 runs written singly undergo 4 merges → ascending; the 9 merged runs undergo 1 preliminary (order‑preserving) merge + 4 read‑backward merges = 5 merges, but because the preliminary merge is order‑preserving, the net effect of the 4 read‑backward merges is ascending. Hence the final output is ascending.

For (S = 4) we would use the perfect distribution of level 2 directly (no preliminary merges). For (S = 6) we again use level 4 with (D = 8) preliminary merges, etc.

The construction matches the requirement “merge some, but not all, of the runs twice” (the merged runs are effectively merged twice: once in the preliminary order‑preserving merge, and once in each of the cascade passes). The total number of read‑backward merge passes remains even, so the output is ascending. This completes the proof. ∎