runtime - 什么时候插入排序比合并排序快？

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”表示以对数为底的二。

（除此之外：这样的计算并不能真正转化为任何一种算法会击败另一种算法的现实迹象。说真的，正好是 43？）

Answer 2

这是 Cormen 第 3 版算法导论中的第二个练习题。对于算法的新手来说，这个方程的解并不是那么简单：

当 8n^2 < 64n lg n 、 n < 8 lg n 、 2^ n/8 < n 时，插入排序优于合并排序。这适用于 2 <= n <= 43（通过使用计算器找到）。因此，我们可以将归并排序重写为对 43 或更小的输入使用插入排序，以提高运行时间。