Java Reference
In-Depth Information
first eight runs from T1 to T2 and then perform the merge. This approach adds an
extra half pass for every pass that we make. The question is, can we do better?
An alternative method is to split the original 34 runs unevenly. If we put
21 runs on T2 and 13 runs on T3, we could merge 13 runs on T1 before T3
was empty. We could then rewind T1 and T3 and merge T1, with 13 runs, and
T2, with 8 runs, on T3. Next, we could merge 8 runs until T2 was empty, leav-
ing 5 runs on T1 and 8 runs on T3. We could then merge T1 and T3, and so on.
Figure 21.37 shows the number of runs on each tape after each pass.
The original distribution of runs makes a great deal of difference. For
instance, if 22 runs are placed on T2, with 12 on T3, after the first merge we
obtain 12 runs on T1 and 10 runs on T2. After another merge, there are
10 runs on T1 and 2 runs on T3. At this point, the going gets slow because we
can merge only two sets of runs before T3 is exhausted. Then T1 has 8 runs and
T2 has 2 runs. Again we can merge only two sets of runs, obtaining T1 with
6 runs and T3 with 2 runs. After three more passes, T2 has 2 runs and the
other tapes are empty. We must copy 1 run to another tape. Then we can finish
the merge.
Our first distribution turns out to be optimal. If the number of runs is a
Fibonacci number,
F
N
,
the best way to distribute them is to split them into two
Fibonacci numbers,
F
N
- 1
and
F
N
- 2
. Otherwise, the tape must be padded with
dummy runs in order to increase the number of runs to a Fibonacci number. We
leave the details of how to place the initial set of runs on the tapes for you to handle
as Exercise 21.22. We can extend this technique to a
K
-way merge, in which we
need
K
th-order Fibonacci numbers for the distribution. The
K
th-order Fibonacci
number is defined as the sum of the
K
previous
K
th-order Fibonacci numbers:
The distribution of
runs affects perfor-
mance. The best
distribution is
related to the
Fibonacci
numbers.
…
F
()
N
=
F
()
0
NK
2
()
F
()
N
1
(
-
)
+
F
()
N
2
(
-
)
+
+
F
()
NK
(
-
)
(
≤≤
-
)
=
0
F
()
K
1
(
-
)
=
1
After
Run Const.
T3 + T2
T1 + T2
T1 + T3
T2 + T3
T1 + T2
T1 + T3
T2 + T3
T1
T2
T3
0
21
13
13
8
0
5
0
8
0
5
3
3
2
0
1
0
2
0
1
1
1
0
0
figure 21.37
The number of runs for a polyphase merge
Search WWH ::
Custom Search