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

Question

在一道作业问题中，我被告知插入排序的运行时间为8n²，归并排序的运行时间为64(n(lg n))。在给出的解决方案中，它说只要n≤43，插入排序就比归并排序快，但老师的答案并没有真正解释为什么或者他是如何得出43的。有人能解释一下吗？我对计算运行时间不是很擅长，所以我正在努力更好地理解。是的，我试着问老师，但我还是感到困惑。任何帮助都将不胜感激！谢谢！

- Lost

---

请直接提问，避免添加故事。 - Sushant Gupta

可以，为什么n要小于等于43？ - Lost

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

(顺便说一下：这样的计算实际上并不能真正转化为任何一个算法将会击败另一个算法的现实指示。说真的，恰好是43吗？)

- Ray Toal

---

8n^2 <= 64n lg n 这个不等式是怎么来的？ - Pavel Podlipensky

这些值来自问题。我猜8和64是一些任意分配给我们在进行渐近分析时看到的模糊常数的具体值，只是为了让问题有一些具体的值。 - Ray Toal

我是指在这种情况下数学是如何运作的：“n^2 <= 8n lg n”？但是，“n^2 >= n lg n”。 - Pavel Podlipensky

对于某些n的值，它将是<=，而对于其他n的值，它将是>=。要做的事情是找到截止点。 - Ray Toal

Answer 2

这是Cormen的《算法导论》第三版中的第二个练习问题。对于算法新手来说，解决这个方程并不那么直截了当：

当8n^2 < 64n lg n, n < 8 lg n, 2^n/8 < n时，插入排序比归并排序更快。通过计算器可以发现，对于2 ≤ n ≤ 43，这是正确的。因此，我们可以重新编写归并排序，以便在输入大小为43或更小的情况下使用插入排序，以改善运行时间。

- Sahil Babbar