when is insertion sort faster than merge sort?

问题:

For a homework problem, I was told that insertion sort runs at 8n^2 and that merge sort runs at 64(n(lg n)). As part of the solution I was given, it said that insertion sort was faster than merge sort as long as n <= 43, but the teacher's answer doesn't really explain why or how he arrived at 43. Can anyone explain this? I'm not that great with figuring out run times so I'm trying to get a better understanding. And yes, I tried asking the teacher, but I was still confused. Any help would be great! thank you!

回答1:

It came from this (algebraic) line of reasoning

steps_in_insertion_sort <= steps_in_merge_sort
8n^2 <= 64n lg n
n^2 <= 8n lg n
n <= 8 lg n

Then 43 works by trial and error, or by solving for the zero of the equation n - 8 lg n = 0.

For hacking by trial and error, note:

$ python
>>> 8 * log(43)/log(2)
43.41011803761678

Because "lg" means log-base-two.

(Aside: calculations like this do not really translate to any real-world indication that one algorithm will beat another. Seriously, exactly 43?)

回答2:

This is the second exercise question in Introduction to Algorithms, 3rd edition by Cormen. The solution to this equation is not so straight forward for a newcomer to algorithms:

Insertion sort beats merge sort when 8n^2 < 64n lg n , n < 8 lg n , 2^ n/8 < n . This is true for 2 <= n <= 43 (found by using a calculator). Therefore, we can rewrite merge sort to use insertion sort for input of size 43 or less in order to improve the running time.