We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small enough size of K, switching to insertion sort would be faster.

I have tested this with Python, and each time within increasing factor of 10 number of data, the hybrid algorithm always take lesser number of swaps and perform slightly faster.

My question is, how can I analyze this algorithm in terms of its complexity, since it's mixed?

The height will no longer be log(n), since now with the threshold K, we will not continue dividing the array. I'm not sure how I can write this? O(n * log(not sure what to write))? And, since the moment it reaches the threshold, it will be n operations that is done by insertion sort. So I'm thinking:

O(n * log(not sure what to write) + n )?

  • $\begingroup$ Questions to answer yourself: a) Is not sure what to write greater than 1? If it is, what use is + n? b) Is threshold $K$ independent of $n$? If it is, how can you account for it in an "asymptotic resource requirements" assessment based on mergesorts? $\endgroup$
    – greybeard
    Aug 29, 2021 at 10:07
  • $\begingroup$ (The height will no longer be log(n) is it $\Theta(\log n)$?) $\endgroup$
    – greybeard
    Aug 29, 2021 at 11:23
  • 1
    $\begingroup$ Please don't delete your question and reupload it. As someone wrote on your previous question - if the threshold $k$ is constant, then the algorithm is still $O(n\log(n))$ asymptotically since we don't really care about constants that much. Otherwise, the running time is $O\left( K^2+n\log \left(\frac{n}{K}\right)\right)$. Its definitely not a speedup in terms of complexity. $\endgroup$
    – nir shahar
    Aug 29, 2021 at 11:26


Your Answer

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