# Analyzing Hybrid Merge and Insertion Sort

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 )?

• 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? Aug 29 at 10:07
• (The height will no longer be log(n) is it $\Theta(\log n)$?) Aug 29 at 11:23
• 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. Aug 29 at 11:26