TAOCP 5.4.1 Exercise 18

Section 5.4.1: Multiway Merging and Replacement Selection

Exercise 18. [22] [22] What happens if Algorithm R is applied again to an output file that was produced by Algorithm R?

Verified: no
Solve time: 1m41s

Solution

Let the output of Algorithm R be the sequence of records obtained from the input file, with each record carrying an extended key $(S,K)$, where $S$ is the run number assigned during replacement selection and $K$ is the original key. The algorithm outputs records in lexicographic order on $(S,K)$, with $S$ as major key and $K$ as minor key.

Let the runs in the output file be denoted $R_1, R_2, \dots, R_m$, where every record in $R_i$ has run number $S=i$, and within each $R_i$ the keys $K$ are in nondecreasing order.

Apply Algorithm R again to this output file, using the same value of $P$.

During initialization of the selection tree, the first $P$ records of the file are loaded. Each such record belongs to some run $R_i$, hence carries a run number $S=i$. Let the smallest run number among these $P$ records be $S_{\min}$. Among all records currently in the tree, every record from run $R_{S_{\min}}$ has run number strictly less than every record from $R_j$ with $j>S_{\min}$.

The selection rule of Algorithm R compares keys lexicographically on $(S,K)$. Since $S$ is the major key, any record with smaller run number is selected regardless of $K$. Hence, while any record from run $R_{S_{\min}}$ remains in the tree or can be fed into it from the input stream, no record from a larger run number can be output.

As the algorithm proceeds, whenever a record from run $R_{S_{\min}}$ is output, it is replaced by the next record of the same run, since the input file is a linear concatenation of runs and records are consumed in order. Therefore the tree continues to contain records from run $R_{S_{\min}}$ until that run is exhausted. No record from any $R_j$ with $j>S_{\min}$ is output before all records of $R_{S_{\min}}$ have been removed from the system.

After run $R_{S_{\min}}$ is exhausted, the smallest remaining run number becomes the new minimum among active records, and the same argument applies. The algorithm therefore outputs all records of $R_1$ first, then all records of $R_2$, and so on in increasing order of run number.

Within each run $R_i$, the original order of keys $K$ is nondecreasing, and the algorithm never reorders records inside a single run because all comparisons with other runs are resolved by the run number $S$ before $K$ is considered.

Hence the second application of Algorithm R produces a sequence whose concatenation of runs is

$$ R_1, R_2, \dots, R_m $$

with each $R_i$ unchanged in internal order and unchanged in position.

The output file is therefore identical to the input file produced by the first application of Algorithm R.

This completes the proof. ∎