When do Insertion Sort and Merge Sort have roughly the same efficiency (based on array sorting)

Question

I referenced this question but it doesn't exactly apply to what I'm trying to find.

So I need to find the point at which merge sort and insertion sort perform similarly on an input with i inversions. (I.E. I need to know what % an array needs to be sorted for the two to have similar performance.) Using a graphing calculator I can find that the more the array is sorted the higher the value of n it takes for insertion sort to beat merge sort.

My problem is mainly how I show mathematically when these two have similar performance. As the % sorted approaches 100 the point of beating merge sort becomes closer to 1, and that's where I'm stuck, there is always a point of divergence.

I can set the number of comparisons equal to each other and through a closed form but that doesn't seem to lead anywhere. Can someone advise me on how to solve this?

Average number of swaps of Insertion Sort = $\sum_{i=0}^n i/2 = \frac{(n^2+n)}{4}$

Number of swaps of Merge Sort = $x * log_{2} (x)$

At what point of array sorting are these similar? How do I find this?

Answer 1

The average number of swaps insertion sort makes is (n^2+n)/4 and the number of swaps merge sort makes is n. Merge sorts efficiency remains consistent throughout but Insertion sort changes from O(n^2) to O(n) so the curve must flatten until it becomes linear. Since merge sort is always O(n lg n) we can graph it and the average case (in your picture) and see visually that they are similar. Additionally we can set them equal to each other and learn the following…

Let N = Array with i inversions and i = iterator

n * log2 n = ∑n/2 (N, i = 0)

n * log2 n = .5((n^2+ n)/2)

n * log2 n = (n^2+ n)/4

log2 n = (n+1)/4 log2 n = .25n + .25

From this we can see that ignoring the constant factors, an array of length n with log2 n unsorted elements should follow O(n log n) fairly well for any n.