A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 830

figure 21.35
After one round of
three-way merging
(run length = 9)

A1 11 12 17 28 35 81 4 6 9

A2 15 41 58 75

A3

B1

B2

B3

figure 21.36
After two rounds of
three-way merging

A1

A2

A3

B1 11 12 15 17 28 35 41 58 75 81 4 6 9

B2

B3

After the initial run-construction phase, the number of passes required
using K -way merging is ⎡ log K ( N / M ) ⎤ because the length of the runs gets
K times larger in each pass. For our example, the formula is verified because
. If we have 10 tapes, K = 5. For the large example in Sec-
tion 21.6.3, 320 runs would require

log 13 ⁄ 3 = 2

3

log 320 = 4 passes.

5

21.6.5 polyphase merge

The K -way merging strategy requires the use of 2 K tapes, which could be pro-
hibitive for some applications. We can get by with only K + 1 tapes, called a
polyphase merge. An example is performing two-way merging with only three
tapes.
Suppose that we have three tapes—T1, T2, and T3—and an input file on T1
that can produce 34 runs. One option is to put 17 runs each on T2 and T3. We
could then merge this result onto T1, thereby obtaining one tape with 17 runs. The
problem is that, as all the runs are on one tape, we must now put some of these
runs on T2 to perform another merge. The logical way to do that is to copy the

The polyphase
merge implements
a K -way merge with
K + 1 tapes