TAOCP 5.4.1 Exercise 7
Algorithm R initializes the selection tree by filling all external nodes with the next input records.
Section 5.4.1: Multiway Merging and Replacement Selection
Exercise 7. [**] [17| What does Algorithm R do when there is no input at all?
Verified: yes
Solve time: 1m23s
Algorithm R initializes the selection tree by filling all external nodes with the next input records. When the input stream contains no records, every external node is filled with the sentinel key $\infty$ (written $\text{oo}$ in the text). Since all keys in the tree are equal and represent $\infty$, the winner of every comparison is also $\infty$, so the root of the tree is $\infty$ at initialization.
The algorithm then attempts to output the smallest key, which is $\infty$. In replacement selection, a record whose key is $\infty$ is not treated as a data record but as a boundary condition indicating that no further records remain in the current run. Because no real key is ever introduced into the tree, no replacement by actual input occurs, and no finite key is ever selected for output. The process therefore terminates immediately after recognizing that the initial state contains no input records.
The output consists of no records at all; no run is produced. ∎