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