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

figure 21.33
Tapes after the third
round of merging

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

A2

B1

B2

would then need nine more passes to complete the sort. This formula also cor-
rectly tells us that our example in Figure 21.30 requires

⎡

log(13/3)

⎤

, or three

more passes.

21.6.4 multiway merge

If we have extra tapes, we can reduce the number of passes required to sort
our input with a multiway (or K -way) merge . We do so by extending the basic
(two-way) merge to a K -way merge and use 2 K tapes.
Merging two runs is done by winding each input tape to the beginning of
each run. Then the smaller element is found and placed on an output tape, and
the appropriate input tape is advanced. If there are K input tapes, this strategy
works in the same way; the only difference is that finding the smallest of the
K elements is slightly more complicated. We can do so by using a priority
queue. To obtain the next element to write on the output tape, we perform a
deleteMin operation. The appropriate input tape is advanced, and if the run on
that input tape has not yet been completed, we insert the new element in the
priority queue. Figure 21.34 shows how the input from the previous example
is distributed onto three tapes. Figures 21.35 and 21.36 show the two passes
of three-way merging that complete the sort.

K -way merging
reduces the num-
ber of passes. The
obvious implemen-
tation uses 2 K
tapes.

figure 21.34
Initial distribution of
length 3 runs to three
tapes

A1

A2

A3

B1 11 81 4 1 8 75

B2 12 35 96 15

B3 17 28 99