TAOCP 5.4.1 Exercise 1
After Step 3 the current front keys of the four runs are $503,\ 170,\ 426,\ 612$ after the replacement of $154$ by $426$.
Section 5.4.1: Multiway Merging and Replacement Selection
Exercise 1. [10] [10] What is Step 4, in the example of four-way merging at the beginning of this section?
Verified: yes
Solve time: 56s
After Step 3 the current front keys of the four runs are
$503,\ 170,\ 426,\ 612$ after the replacement of $154$ by $426$.
The smallest of these is $170$, so Step 3 outputs $170$ and replaces it by $908$ from its run. The four current keys after that update are
$503,\ 908,\ 426,\ 612$.
Step 4 then selects the smallest among these values, which is $426$. This key belongs to the third run. It is output, and it is replaced by the next key in that run, namely $653$.
Thus Step 4 consists of outputting $426$ and updating the third input position by the replacement $426 \leftarrow 653$. The new set of available keys after Step 4 is
$503,\ 908,\ 653,\ 612$. ∎