In mergesort, we need to combine two sorted lists to get one sorted list. We saw how to do this using the procedure merge. Suppose we instead decided to combine the two lists together by first appending the two lists into one list (i.e. the second list is added to the end of the first list) and then running MDD Sort on that combined list, where MDD Sort is the sorting algorithm from HW1.

MergeSort(array A)

{

if A has 0 or 1 elements then return(A) else

{

split A into Left and Right

MergeSort(Left)

MergeSort(Right)

Do MDD Sort on (Right appended to the end of Left).

}

}

You can assume that n, the number of elements in the original array, is a power of 2. You have to do the following:

(a) Give a recurrence relation for the running time of MergeSort.

b) Using the Master theorem, solve this recurrence relation.

Make sure you solve the time complexity. I think it is N^2