Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of recursion, it switches over to insertion sort. What is the running time of this modified algorithm?

I know that MergeSort has worst-case runtime of $O(n \log n)$ and Insertion Sort has worst-case runtime of $O(n^2)$, but I'm not sure how these bounds will be affected within the problem above.

  • 1
    $\begingroup$ Set up the recurrence and solve it. $\endgroup$ – Raphael Oct 9 '14 at 8:21

You know that MergeSort has a complexity of $O(n\log n)$. Why? We can write a recurrence for the running time of MergeSort: $$ T(n) = 2T(n/2) + Cn, \quad T(1) = D. $$ (Assume for simplicity that $n$ is a power of 2.) The solution is $T(n) = O(n\log n)$. Why? Since we can write $$ T(n) = 2T(n/2) + Cn = 4T(n/4) + Cn + Cn = 8T(n/8) + Cn + Cn + Cn = \cdots = (\log n)Cn + Dn. $$ That is, at each internal level the total complexity is $Cn$, there are $\log n$ levels, and at the bottom the complexity is $Dn$. It is instructive to rewrite it in terms of $n = 2^k$: $$ T(2^k) = 2^1T(2^{k-1}) + C2^k = 2^2T(2^{k-2}) + C2^k + C2^k = \cdots. $$ In your case, you want to stop the recursion at depth $k/2$, and instead of expanding $2^{k/2}T(2^{k/2})$ using the recursion, apply the $En^2$ insertion sort algorithm. What would you get? (that's a question for you)


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.