Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and derive the closed-form formula for sorting time Tk(n) of the modified merge sort for an arbitrary k. Then determine whether the modified merge sort could be faster for some k > 2 than the conventional one (k =2) with the sorting time T2(n) = cn log2n.
So I started by doing the following:
Each time when we split an array into 2 we get T(n/2) in the equation. So first time n/2, then for next we divide 2 again which is (n/2)/2.
Therefore from this we can get 2T(n/2) + cn.
What I don’t understand is what to do next I also did some working to get T2(n) = cnlog2n which I don’t think is useful for the moment, am just confused on what the next step is.