Analysis of Algorithms : An Active Learning Approach

3.8 EXTERNAL POLYPHASE MERGE SORT 99

■ 3.8.1 Number of Comparisons in Run Construction
Because the algorithm used for the run construction phase is not specified, we
will assume that an O(N lg N) sort is used. Because there are S elements in
each run, each one will take O(S lg S) to construct. There are R runs, giving
O(RS lg S) = O(N lg S) comparisons in total for the construction of all of
the runs. The run construction phase is O(N lg S).

■ 3.8.2 Number of Comparisons in Run Merge
In Section 3.6.1, we saw that MergeLists does A + B
1 comparisons in
the worst case with two lists of A and B elements. In our case, we have R runs
of size S on the first pass that get merged, so there are R / 2 merges, each of
which will take at most 2S
1 comparisons, or R / 2 (2S
1) = RS

R / 2 comparisons. On the second pass, we have R / 2 runs of size 2S, so there
are R / 4 merges, each of which will take at most 2(2S)
1 comparisons,
orR / 4 (4S
1) = RS
R / 4 comparisons. On the third pass, we have
R / 4 runs of size 4S, so there are R / 8 merges, each of which will take at most
2(4S)
1 comparisons, or R / 8 (8S
1) = RS
R / 8 comparisons.
If we recall that there will be lg R merge passes, the total number of com-
parisons in the merge phase will be

In the second equation, you should note that if you add 1/2 + 1/4 + 1/8 +,

.. ., you will get a number that is less than 1, but it will get closer to 1 the
more terms that you have. To visualize this, imagine that you stand 1 foot away
from a wall, and you repeatedly keep moving closer to the wall by one-half
your current distance from the wall. Because you only move one-half the dis-
tance each step, you will never reach the wall, but you will keep getting closer
to it. In the same way, if you do the above addition, you are adding one-half
the distance between your current total and the number 1 each time. This
means that the sum will keep getting closer to 1, but never larger. This can also
be shown by the application of Equation 1.18 using A = 0.5 and an adjustment

()RSR* – ⁄ 2 i

i=1

lgR

∑ ()RS*

i=1

lgR

∑ R^2

()⁄ i

i=1

lgR

= –∑

()RS* lgRR– 12 ⁄ i

i=1

lgR

= **∑

≈()RS* *lgRR–

=NlgRR–