Need help analyzing a merge sort

Question

Im working on trying to understand merge sorts better and had a professor give me this to try to help. It is finals week and I have been trying to walk through this problem but have been having trouble. If someone could walk me through this explaining things, that would be greatly appreciated.

I. Worst Case Performance of Merge Sort I want you to come up with the correct recurrence relation for the number of comparisons $T(n)$ for the merge sort in the worst case scenario. Where $n$ is the size of the array to be sorted. For this problem we will assume that our array to be sorted is always of size $n = 2k$ for some integer $k > 0$.I shall give you four choices for $T(n)$. You need to pick the correct one and explain why you chose it. The worst case scenario means when you merge smaller sorted arrays to obtain bigger sorted arrays you need to do a maximum number of comparisons. To help you understand the concept I am giving below an example of an array of size $n = 23$. The following shows the process of subdividing array into subgroups until each subgroup size is one when it unnecessary to do any comparisons.

Given [20, 30, 40, 50, 60, 70, 80, 90]

Step 1 [20, 30, 40, 50] [60 70 80 90]

Step 2 [20, 30] [40, 50] [60, 70] [80, 90]

Step 3 [20] [30] [40] [50] [60] [70] [80] [90]

Merging involves combining smaller groups into sorted bigger groups as shown in the following steps.

`[20]   [30]    [40]    [50]    [60]    [70]    [80]    [90]`

Step 4 [30, 20] [60, 50] [70, 60] [90, 80]

Step 5 [50, 40, 30, 20] [90, 80, 70, 60]

Step 6 [90, 80, 70, 60, 50, 40, 30, 20]

Notice that to obtain arrays in step $4$ through step $6$ we need to do maximum comparisons. So this is a worst case scenario. To obtain the required recurrence relation you only need to think about the sizes of the given array, sizes of the array in step $1$, the number of comparisons needed to obtain the final array in step $6$ from the arrays in step $5$. So these are your four choices:

A. $T(n) = n + T(n/2)$

B. $T(n) = n/2 -1 + 2T(n/2)$

C. $T(n) = n/2 + T(n/2)$

D. $T(n) = n-1 + T(n-1)$

Select the correct answer with full explanation.

Answer 1

$T(n) = 2T(n/2) + n$ This will be the breakdown because you need to divide the problem with $n$ elements into two problems of size $n/2$ elements and after doing the sort on these two two smaller problems you have to again have a pass on the whole $n$ elements ( this is the merge step ) .

Therefore a problem of size $n$ takes $T(n) = 2T(n/2) + n $ where $n$ is for the merge step and $2T(n/2)$ is for "divide the problem into two smaller problems of equal size".

Looking at the options , only the option which has $2T(n/2)$ should be correct !

Answer 2

Consider an array of size $n$. To sort it via merge sort, we perform the following steps:

• Divide: We split the array into two subarrays, each of size $n/2$. This takes $\Theta(1)$ steps.

• Conquer: We sort each subarray. This takes $2 \cdot T(n/2)$ steps.

• Combine: We merge the two sorted subarrays to obtain our original sorted array. Assuming that we must compare each element in the array, this takes $\Theta(n)$ steps.

Putting everything together, we get $T(n) = 2 \cdot T(n/2) + \Theta(n)$. Looking at your options, the only choice that matches this is $B$.