TAOCP 5.4.7 Exercise 7

Exercise 7. [21] [21] Does the duality principle apply also to multireel files?

*5.4.8. Two-Tape Sorting

Since we need three tapes to carry out a merge process without excessive tape motion, it is interesting to speculate about how we could perform a reasonable external sort using only two tapes.

One approach, suggested by H. B. Demuth in 1956, is sort of a combined replacement-selection and bubble sort. Assume that the input is on tape T1, and begin by reading P + 1 records into memory. Now output the record whose key is smallest, to tape T2, and replace it by the next input record. Continue outputting a record whose key is currently the smallest in memory, maintaining a selection tree or a priority queue of P+ 1 elements. When the input is finally exhausted, the largest P keys of the file will be present in memory; output them in ascending order. Now rewind both tapes and repeat the process by reading from T2 and writing to T1; each such pass puts at least P more records into their proper place. A simple test can be built into the program that determines when the entire file is in sort. At most [(N, 1)/P] passes will be necessary.

Verified: yes
Solve time: 1m02s

Solution

A multireel file consists of a finite sequence of reels, each reel being a sequential medium on which records are read and written in forward order, with a forced change of reel when an end is reached. The operational constraints on a single reel are identical to those of a tape segment: access is sequential, and reversal of direction requires a physical repositioning equivalent to rewind.

The duality principle between radix distribution patterns and merge patterns, as developed in Section 5.4.7, depends only on the following structural properties: each data item is processed through a finite rooted tree of distribution or merging steps; each step respects a FIFO constraint induced by sequential output order; and the feasibility of a pattern is determined entirely by the ordering constraints imposed by these FIFO conditions. These conditions characterize strongly $T$-fifo trees in the sense of Section 5.4.4.

Let a multireel file be treated as a single tape whose content is partitioned into contiguous blocks, each block corresponding to a reel. Within each block, the FIFO discipline holds exactly as for an ordinary tape. Transitions between reels introduce additional boundary points, but these points do not alter the relative ordering constraints among records produced within any fixed processing step, since all output within a step is still written sequentially on a single active reel.

Time reversal in the duality argument replaces each distribution step by a merge step in reverse order while preserving the FIFO constraint on each output medium. Reversing a multireel process also reverses the order of reels but preserves the internal sequential structure of each reel. Hence the reversed process again satisfies the same local FIFO conditions on each reel, and the global feasibility condition is unchanged.

Since the characterization of allowable patterns in Section 5.4.7 depends only on FIFO ordering constraints and not on whether a tape consists of one reel or several concatenated reels, every valid multireel radix distribution pattern corresponds bijectively to a valid multireel merge pattern under time reversal. The correspondence between strongly $T$-fifo trees and admissible distribution patterns therefore remains intact when each tape is replaced by a multireel file.

Thus the duality principle extends without modification to multireel files.

This completes the proof. ∎