TAOCP 5.4.4 Exercise 1
In read-forward merging, runs are written in ascending order and each run is terminated by an artificial sentinel record with key $+\infty$.
Section 5.4.4: Reading Tape Backwards
Exercise 1. [17] It is often convenient, during read-forward merging, to mark the end of each run on tape by including an artificial sentinel record whose key is $+\infty$. How should this practice be modified, when reading backwards?
Verified: no
Solve time: 4m31s
Solution
In read-forward merging, runs are written in ascending order and each run is terminated by an artificial sentinel record with key $+\infty$. When the tape is read forward, the sentinel appears after all data records of the run; because every data key is strictly less than $+\infty$, the sentinel correctly marks the end of the run during a merge.
When reading backwards, the tape is scanned from the end toward the beginning. A run that was written in ascending order ($A$ run) is now encountered in descending order; a run written in descending order ($D$ run) is encountered in ascending order. The “end” of a run from the perspective of the read direction is therefore the beginning of the run as written. Hence the sentinel must be placed at the beginning of each run when it is written.
Furthermore, the sentinel key must be chosen to terminate the merge correctly for the order in which the run is read:
- For an $A$ run (ascending on tape), reading backwards yields a descending sequence. A descending merge stops when a key smaller than all data keys is seen; thus the sentinel should be $-\infty$.
- For a $D$ run (descending on tape), reading backwards yields an ascending sequence. An ascending merge stops when a key larger than all data keys is seen; thus the sentinel should be $+\infty$.
The read-backward merge patterns described in the section (balanced, polyphase, cascade) produce alternating $A$ and $D$ runs on each tape. Consequently, the sentinels must alternate in the same way: write a $-\infty$ sentinel at the start of every $A$ run, and a $+\infty$ sentinel at the start of every $D$ run. This guarantees that during a backwards read each run is properly delimited by a sentinel appropriate for its reading order.
\boxed{\text{Place the sentinel at the beginning of each run. Use $-\infty$ for ascending runs ($A$) and $+\infty$ for descending runs ($D$).}}