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.

  • $\begingroup$ I think $c(k-1)n$ for merging is bad and this even calls for it never to be better than a standard implementation. From my short thinking, you can speed-up merging, by managing a sorted array of current pointers, so the whole merging time falls to $c n \log k$ (for insertion of next element, after minimal was picked). $\endgroup$
    – dEmigOd
    Apr 14 '18 at 5:16

You can in the iterative manner, just substitute the recurrence expression back

So you have a basic $$T(n) = 2T\left(\frac{n}{2}\right) + cn$$

Therefore, for any $k$ $$T\left(\frac{n}{2^k}\right) = 2T\left(\frac{n}{2^{k+1}}\right) + c\cdot\frac{n}{2^k}$$

So, $$T(n) = 2T\left(\frac{n}{2}\right) + cn =$$ $$ = 2\left(2T\left(\frac{n}{4}\right) + c\cdot\frac{n}{2}\right) + c\cdot n = $$ $$ 4T\left(\frac{n}{4}\right) + 2c\cdot n = \ldots = 2^kT\left(\frac{n}{2^k}\right) + kcn$$

Here, you should think "how deep you can go in the recursion?". Recall, in mergesort, the array of size $1$ is sorted and we stop diving.

I.e. $T\left(\frac{n}{2^{k_{\text{max}}}}\right) = T(1)$, then $k_{\text{max}} = \log n$.

This concludes in $$T(n) = 2^{k_{\text{max}}}T(1) + k_{\text{max}}cn = nT(1) + cn\log n$$

$T(1)$ is some constant.

Regarding this $k$-split. No matter, how optimal you are making it, we know you can't theoretically drop under $\Theta(n \log n)$, why bother than?

  • 1
    $\begingroup$ Thank you! makes much more sense now $\endgroup$
    – M.Jones
    Apr 14 '18 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.