TAOCP 5.2.4 Exercise 4
Let the records be stored in three contiguous segments of $N$ locations each, denoted $A_1,\ldots,A_N$, $B_1,\ldots,B_N$, and $C_1,\ldots,C_N$.
Section 5.2.4: Sorting by Merging
Exercise 4. [**] [25] (D. A. Bell.) Show that sequentially allocated straight two-way merging can be done with at most $3N$ memory locations, instead of $2N$ as in Algorithm S.
Verified: yes
Solve time: 1m09s
Let the records be stored in three contiguous segments of $N$ locations each, denoted $A_1,\ldots,A_N$, $B_1,\ldots,B_N$, and $C_1,\ldots,C_N$. At the beginning of a pass, two segments contain the input files in the sense of Algorithm S, while the third segment is unused. The merging procedure of Algorithm S is then carried out exactly as written, except that every write operation $R_k \leftarrow R_i$ or $R_k \leftarrow R_j$ is directed into the currently designated output segment. The indices $i$ and $j$ always refer to the two input segments, and $k$ always ranges over the output segment, so no location outside the three segments is ever referenced.
During a pass, only two segments are simultaneously read as sources, and only one segment is written as destination. After completion of the pass, the roles of the three segments are rotated cyclically so that the output segment becomes one of the input segments for the next pass, and one of the previous input segments becomes the new output segment. Since at no time are more than $N$ locations needed for each of the three segments, the total number of memory locations required is at most $3N$, and no step of the algorithm requires storage outside these segments. This completes the proof. ∎