TAOCP 5.2.5 Exercise 3
At the start, Algorithm H sets $i \leftarrow 0$ and then sets $P \leftarrow \mathrm{TOP}[0]$.
Section 5.2.5: Sorting by Distribution
Exercise 3. [**] [15] Explain why Algorithm H makes BOTM[0] point to the first record in the “hooked-up” queue, even though pile 0 might be empty.
Verified: yes
Solve time: 1m30s
At the start, Algorithm H sets $i \leftarrow 0$ and then sets $P \leftarrow \mathrm{TOP}[0]$. By the conventions of Algorithm R, $\mathrm{TOP}[0]$ initially refers to $\mathrm{BOTM}[0]$, so $P$ begins at the head pointer of the final list being constructed.
If pile $0$ is empty, then $\mathrm{BOTM}[0]=\Lambda$, and the algorithm proceeds with $i \leftarrow 1,2,\dots$ until the first index $j$ such that $\mathrm{BOTM}[j]\neq \Lambda$. For every empty pile index $i<j$, step H4 causes control to return to H3 without executing H5, so no links are created during these iterations.
When the first nonempty pile $j$ is reached, step H2 sets $P \leftarrow \mathrm{TOP}[j]$, which is the first element of pile $j$. Since all earlier piles were empty, no prior execution of H5 has altered the link structure starting from $\mathrm{TOP}[0]=\mathrm{BOTM}[0]$, so $P$ still corresponds to the initial head pointer.
On the next increment of $i$, step H5 is executed with the previous value of $P$, which is still $\mathrm{BOTM}[0]$, giving $\mathrm{LINK}(\mathrm{BOTM}[0]) \leftarrow \mathrm{BOTM}[j]$. Thus the first nonempty pile encountered is attached directly after $\mathrm{BOTM}[0]$, so $\mathrm{BOTM}[0]$ becomes the first record of the hooked-up queue even when pile $0$ is empty. This completes the argument. ∎