Analysis of Algorithms : An Active Learning Approach

3.6 MERGE SORT 87

zero. Because middle is calculated to be exactly between first and last,
we see that we are breaking the list into two sublists, and each one is half the
size of the original. If the list has N elements, we create two sublists with N / 2
elements. Based on the analysis of MergeLists, this means that the combine
step will take N / 2 comparisons in the best case, and N / 2 + N / 2
1, or
N
1, comparisons in the worst case. Putting all of this together gives the two
recurrence relations for the worst (W) and best (B) cases.

We now apply the techniques of Section 1.6 to solve these recurrence rela-
tions. First, we solve the worst case:

Now we substitute:

We see that the coefficient of W increases at the same rate as the denominator
increases. Eventually, this term will become W(1), which has a value of zero, and
so this first term will eventually disappear. Notice that each substitution pro-
duced another addition of N and the subtraction of the next higher power of 2.
How many of these will be included? We see in the last equation that we have

WN()= 2 WN()⁄ 2 +N– 1

W() 0 ==W() 1 0

BN()= 2 BN()⁄ 2 +N⁄ 2

B() 0 ==B() 1 0

WN()⁄ 2 = 2 WN()⁄ 4 +N⁄ 21 –

WN()⁄ 4 = 2 WN()⁄ 8 +N⁄ 4 – 1

WN()⁄ 8 = 2 WN()⁄ 16 +N⁄ 8 – 1

WN()⁄ 16 = 2 WN()⁄ 32 +N⁄ 16 – 1

WN()= 2 WN()⁄ 2 +N– 1

WN()= 22 ()WN()⁄ 4 +N⁄ 2 – 1 +N– 1

WN()= 4 WN()⁄ 4 ++N– 2 N– 1

WN()= 42 ()WN()⁄ 8 +N⁄ 4 – 1 ++N– 2 N– 1

WN()= 8 WN()⁄ 8 +++N– 4 N– 2 N– 1

WN()= 82 ()WN()⁄ 16 +N⁄ 8 – 1 +++N– 4 N– 2 N– 1

WN()= 16 WN()⁄ 16 ++++N– 8 N– 4 N– 2 N– 1

WN()=16 2()WN()⁄ 32 +N⁄ 16 – 1 ++++N– 8 N– 4 N– 2 N– 1

WN()= 32 WN()⁄ 32 + ++++N– 16 N– 8 N– 4 N– 2 N– 1