3. 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 heap sort on that combined list.

UNHMergeSort(array A)

{

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

else

{

split A into Left and Right

UNHMergeSort(Left)

UNHMergeSort(Right)

Do Heap 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 UNHmergesort.

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

Question is from algorithm design and analysis course