sorting - 为什么插入排序 O(n^2) 在排序小数组 ~ 7 元素时更好。与 Quick Sort 和 Merge Sort 等 O(nlogn) 排序算法相比？

Question

我看到的:首先，我阅读了另外两个 SO 帖子

1. Why is Insertion sort better than Quick sort for small list of elements?

2. Is there ever a good reason to use Insertion Sort?

但是那里的答案对我来说不够具体。

从这两个帖子的回答中，他们主要指出合并排序和快速排序可能会很慢，因为递归函数调用会产生额外的开销。但我想知 Prop 体的阈值 7 是如何设置的？

我的问题:

我想知道为什么截断是大约 7 个元素，其中二次排序算法(如插入排序)比 O(nlogn) 排序算法(如快速排序或归并排序)更快。

• Use insertion sort on small subarrays. Mergesort has too much overhead for tiny subarrays.
• Cutoff to insertion sort for ~ 7 elements.

我从普林斯顿得到这个 lecture slide我认为这是有信誉的足够来源。请参阅合并排序下的第 11 张幻灯片:实际改进部分。

如果您的回答包含数学证明示例，我将不胜感激。

Answer 1

Big-O 只记录随着 n 变大而起主导作用的因素。它忽略了常数因子和次要项，它们几乎总是存在并且在 n 小时更重要。因此，Big-O 对于比较只需要处理微小输入的算法几乎毫无用处。

例如，您可以有一个 O(n log n) 函数和一个像 t = 5n log n + 2n + 3 这样的时间图，以及一个 O(n^2) 函数，它的时间图类似于 t = 0.5n^2 + n + 2。

比较这两个图，您会发现尽管有 Big-O，O(n^2) 函数会稍微快一些，直到 n 达到大约 13。