when is insertion sort faster than merge sort?

Question

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!

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