Analysis of Algorithms : An Active Learning Approach

88 SORTING ALGORITHMS

five N terms, the sum of the powers of 2 from 0 (1 = 2^0 ) through 4 (16 = 2^4 ) and

W(N / 32) = W(N / 2^5 ). This means that when we get to the point of having

W(N / 2lgN) = W(N / N), the closed form of this equation becomes

This means that W(N) = O(N lg N). When we look at W(N) and B(N), we see

the difference between the two is that N becomes N / 2. When we look at the

role that N played during our substitutions, the reader should see that B(N)


(N lg N) / 2, so it is also the case that B(N) = O(N lg N).

This means that MergeSort is a very efficient sort, even in the worst case,

but the problem is that the MergeList function needs extra space to accom-

plish the merge.

3.6.3

1. Show the results of each pass of MergeSort applied to the list [7, 3, 9, 4, 2,
   5, 6, 1, 8].


2. Show the results of each pass of MergeSort applied to the list [3, 5, 2, 9, 8,
   1, 6, 4, 7].


3. In the discussion of MergeLists, it was mentioned that the best case is
   when all of the values of list A are smaller than the values of list B. This,
   however, doesn’t say anything about the operation of the entire algorithm
   for any initial input of values. Exactly how many key comparisons will be
   done by MergeSort on the list [1, 2, 3, 4, 5, 6, 7, 8]? In general, how
   many comparisons are done for a list of N elements that is already in
   increasing order? Show details of all work.


4. Exactly how many key comparisons will be done by MergeSort on the list
   [8, 7, 6, 5, 4, 3, 2, 1]? In general, how many comparisons are done for a list
   ofN elements that is in decreasing order? Show details of all work.


5. Create an ordering of the numbers 1 through 8 that will cause MergeSort
   to do the worst-case number of comparisons of 17. (Hint: Work backward
   through the sorting process.)

WN() NW* () 1 NlgN 2 i

i=0

lgN–1

= + – ∑

WN()= NlgN–() 2 lgN– 1

WN()= NlgNN– + 1

■3.6.3 EXERCISES