Analysis of Algorithms : An Active Learning Approach

3.6 MERGE SORT 83

3.5.3

1. Given the list of elements, [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4], what
   would be their order after the loop for the heap construction phase exe-
   cutes?


2. Given the list of elements, [3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1], what
   would be their order after the loop for the heap construction phase exe-
   cutes?


3. We could shorten the second for loop in our heapsort by changing the
   ending condition to i≥ 3. What, if anything, would need to be added after
   thisfor loop to assure that the final list is sorted? Would this change reduce
   the number of comparisons (give a detailed reason for your answer)?


4. Prove that a list in reverse order is a heap.

3.6 Merge Sort

Merge sort is the first of our recursive sort algorithms. It is based on the idea

that merging two sorted lists can be done quickly. Because a list with just one

element is sorted, merge sort will break a list down into one-element pieces

and then sort as it merges those pieces back together. All of the work for this

algorithm, therefore, occurs in the merging of the two lists.

Merge sort can be written as a recursive algorithm that does its work on the

way up in the recursive process. In looking at the algorithm that follows, you

will notice that it breaks the list in half as long as first is less than last. When we

get to a point where first and last are equal, we have a list of one element,

which is inherently sorted. When we return from the two calls to MergeSort

that have lists of size 1, we then call MergeLists to put those together to cre-

ate a sorted list of size 2. At the next level up, we will have two lists of size 2

that get merged into one sorted list of size 4. This process continues until we

get to the top call, which merges the two sorted halves of the list back into one

sorted list. We see that MergeSort breaks a list in halves on the way down in

the recursive process and then puts the sorted halves together on the way back

up. The algorithm to accomplish this is

MergeSort( list, first, last )
list the elements to be put into order
first the index of the first element in the part of list to sort

■3.5.3 EXERCISES