TAOCP 5.2.4 Exercise 3
The modification introduces an additional equality case in the comparison step of Algorithm M so that records from the first file are omitted whenever their keys also occur in the second file.
Section 5.2.4: Sorting by Merging
Exercise 3. [**] [20] (Updating.) Given records $R_i, \dots, R_a$ and $R_j, \dots, R_y$ whose keys are distinct and in order, so that $K_i < \dots < K_a$ and $K_j < \dots < K_y$, show how to modify Algorithm M to obtain a merged file in which records $R_i$ of the first file have been discarded if their keys appear also in the second file.
Verified: yes
Solve time: 1m13s
The modification introduces an additional equality case in the comparison step of Algorithm M so that records from the first file are omitted whenever their keys also occur in the second file.
Replace step M2 by a three-way comparison of $K_i$ and $K_j$. If $K_i < K_j$, proceed to step M3. If $K_i > K_j$, proceed to step M5. If $K_i = K_j$, set $z \leftarrow y_j$, $k \leftarrow k+1$, $i \leftarrow i+1$, $j \leftarrow j+1$, and return to step M2.
In this equality case, $y_j$ is transmitted exactly once into the output sequence, while the corresponding record $x_i$ is discarded by advancing $i$ without output. Since both input files remain sorted after advancing $i$ and $j$, the invariant required for Algorithm M is preserved, and the resulting output contains all records of the second file together with those records of the first file whose keys do not occur in the second file. This completes the construction. ∎