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?

enter image description here

  • $\begingroup$ You could just plot the two functions. I seem to recall the figure of merit for sorting is the number of comparisons, not the number of swaps. That may depend less on how sorted the array starts out. $\endgroup$ – Ross Millikan Feb 9 '18 at 5:43
  • $\begingroup$ It seems I was just supposed to show graphically that the average case for insertion sort is about the same as merge sort. $\endgroup$ – Legion Daeth Feb 9 '18 at 6:21

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.


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.