TAOCP 5.4 Exercise 2
For the 3-tape balanced merge with \(P=2\), the initial distribution onto the left bank (Tapes 1 and 2) is exactly as in the 4-tape case: \[ \begin{aligned} \text{Tape 1}\qquad & R_1 \ldots R_{1000000...
Exercise 2. [10] What will the sequence of tape contents be, analogous to (1) through (3), when the example records $R_1 R_2 \ldots R_{5000000}$ are sorted using a 3-tape balanced method with $P = 2$? Compare this to the 4-tape merge; how many passes are made over all the data, after the initial distribution of runs?
Verified: no
Solve time: 1m38s
For the 3-tape balanced merge with (P=2), the initial distribution onto the left bank (Tapes 1 and 2) is exactly as in the 4-tape case:
[ \begin{aligned} \text{Tape 1}\qquad & R_1 \ldots R_{1000000};\ R_{2000001} \ldots R_{3000000};\ R_{4000001} \ldots R_{5000000}.\ \text{Tape 2}\qquad & R_{1000001} \ldots R_{2000000};\ R_{3000001} \ldots R_{4000000}.\ \text{Tape 3}\qquad & (\text{empty}) \end{aligned}\eqno(1) ]
The first merging pass performs a 2-way merge from Tapes 1,2 onto Tape 3:
[ \begin{aligned} \text{Tape 1}\qquad & (\text{empty})\ \text{Tape 2}\qquad & (\text{empty})\ \text{Tape 3}\qquad & R_1 \ldots R_{2000000};\ R_{2000001} \ldots R_{4000000};\ R_{4000001} \ldots R_{5000000}. \end{aligned}\eqno(2) ]
The second pass performs a 1-way merge from Tape 3 back to Tapes 1,2, distributing runs alternately:
[ \begin{aligned} \text{Tape 1}\qquad & R_1 \ldots R_{2000000};\ R_{4000001} \ldots R_{5000000}.\ \text{Tape 2}\qquad & R_{2000001} \ldots R_{4000000}.\ \text{Tape 3}\qquad & (\text{empty}) \end{aligned}\eqno(3) ]
The third pass merges 2-way from Tapes 1,2 to Tape 3:
[ \begin{aligned} \text{Tape 1}\qquad & (\text{empty})\ \text{Tape 2}\qquad & (\text{empty})\ \text{Tape 3}\qquad & R_1 \ldots R_{4000000};\ R_{4000001} \ldots R_{5000000}. \end{aligned}\eqno(4) ]
The fourth pass distributes these two runs 1-way to Tapes 1,2:
[ \begin{aligned} \text{Tape 1}\qquad & R_1 \ldots R_{4000000}.\ \text{Tape 2}\qquad & R_{4000001} \ldots R_{5000000}.\ \text{Tape 3}\qquad & (\text{empty}) \end{aligned}\eqno(5) ]
The fifth pass merges the two runs 2-way onto Tape 3, completing the sort:
[ \begin{aligned} \text{Tape 1}\qquad & (\text{empty})\ \text{Tape 2}\qquad & (\text{empty})\ \text{Tape 3}\qquad & R_1 \ldots R_{5000000}. \end{aligned}\eqno(6) ]
The 4-tape balanced merge requires (\lceil \lg 5 \rceil = 3) merging passes, while this 3-tape method with (P=2) requires (2\lceil \lg 5 \rceil - 1 = 5) merging passes.
\boxed{\text{The 3-tape balanced merge with } P=2 \text{ requires 5 merging passes, compared to 3 passes for the 4-tape merge.}}