TAOCP 5.4.6 Exercise 5
Algorithm F forecasts the next input operation by examining the last records currently present in the active buffers.
Section 5.4.6: Practical Considerations for Tape Merging
Exercise 5. [21] [21] When equal keys are present on different files, it is necessary to be very
careful in the forecasting process. Explain why, and show how to avoid difficulty by defining the merging and forecasting operations of Algorithm F more precisely.
342 SORTING 5.4.6
Verified: yes
Solve time: 1m13s
Solution
Algorithm F forecasts the next input operation by examining the last records currently present in the active buffers. The argument given in the text assumes implicitly that these last keys are distinct. When equal keys occur on different files, ambiguity arises.
Suppose that files $i$ and $j$ both contain the key value $K$, and suppose that the last record presently in the current buffer of file $i$ has key $K$, while the last record presently in the current buffer of file $j$ also has key $K$. During the merge itself, some rule must determine whether records from file $i$ or from file $j$ are output first. If the forecasting operation uses a different rule, it may predict the wrong file as the one whose buffer will become empty first.
For example, assume that the merging process outputs records with equal keys according to file number, choosing the smaller file number first. If the forecasting procedure merely compares keys and breaks ties arbitrarily, it might conclude that file $j$ will empty first although the merge actually consumes the remaining records of file $i$ first. The corresponding input command would then be directed to the wrong file, and a shortage of input buffers could occur later. Hence the forecasting operation must employ exactly the same ordering relation as the merge itself.
The difficulty is removed by defining each record to possess a compound key
$$ (\text{key value},\text{file number}), $$
ordered lexicographically. Thus
$$ (K,i)<(L,j) $$
when either $K<L$, or when $K=L$ and $i<j$.
The merging operation of Algorithm F is then defined more precisely as follows. Among the current records available from files $1,\ldots,P$, select the record whose compound key is smallest and output that record. Consequently, records having equal key values are output in increasing order of file number.
The forecasting operation is defined in the same manner. Let $x_i$ denote the last record presently contained in the active buffer for file $i$. Form the compound keys
$$ (\operatorname{key}(x_i),i), \qquad 1\le i\le P. $$
The file whose compound key is smallest is predicted to be the file whose current buffer will become empty first, and the next input command is assigned to that file.
Since the merge and the forecast are governed by the same total ordering, the sequence in which records are removed from the buffers is exactly the sequence assumed by the forecasting process. Therefore the forecast remains correct even when equal keys occur on different files.
This completes the proof.
∎