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.
[20, 30, 40, 50, 60, 70, 80, 90]
[20, 30, 40, 50] [60 70 80 90]
[20, 30] [40, 50] [60, 70] [80, 90]
       
Merging involves combining smaller groups into sorted bigger groups as shown in the following steps.
`       `
[30, 20] [60, 50] [70, 60] [90, 80]
[50, 40, 30, 20] [90, 80, 70, 60]
[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.