何时插入排序比合并排序更快？

Question

对于家庭作业问题,我被告知插入排序运行在8n ^ 2,合并排序运行在64(n(lg n)).作为解决方案的一部分,我得到了,有人说,插入排序快于那种只要合并为N <= 43,但老师的回答并没有真正解释为什么或者他是如何得出43.任何人都可以解释一下吗？我找出运行时间并不是那么好,所以我想要更好地理解.是的,我试过问老师,但我还是很困惑.任何帮助都会很棒!谢谢!

Answer 1

它来自这个(代数)推理线

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

然后43通过反复试验,或通过求解方程零的n - 8 lg n = 0.

对于通过反复试验进行黑客攻击,请注意:

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

因为"lg"表示log-base-two.

(旁白:这样的计算并没有真正转化为任何一种算法会击败另一种算法的现实指示.严重的是,恰好是43？)