为什么java.util.Arrays.sort（Object[]）使用2种排序算法？

重要的是要注意，在实践中，算法并不总是比算法快。这取决于常量和所涉及的范围。（请记住，渐近表示法测量的是相对增长率，而不是绝对速度）。O(N log N)O(N^2)N

对于小的，插入排序实际上确实击败了合并排序。对于几乎排序的数组，它也更快。N

这里有一句话：

尽管它是具有最坏情况时间的基本排序算法之一，但插入排序是首选算法，无论是在数据几乎排序时（因为它是自适应的），还是在问题大小较小（因为它的开销较低）时。O(N^2)

由于这些原因，并且由于插入排序也很稳定，因此插入排序通常用作较高开销的分而治之的排序算法（如合并排序或快速排序）的递归基例（当问题大小较小时）。

以下是最佳排序算法对几乎排序列表论文的另一句话：

直接插入排序最适合小型或非常接近排序的列表

这意味着，在实践中：

• 某些具有较高渐近上限的算法 A₁ 可能比具有较低渐近上限的另一种已知算法 A₂ 更可取
  • 也许A₂太复杂而无法实现
  • 或者也许在考虑的范围内无关紧要N
    • 例如，参见 Coppersmith-Winograd 算法
• 某些混合算法可能会根据输入大小调整不同的算法

相关问题

• 哪种排序算法最适合对几乎完全排序的列表进行重新排序？
• 有没有一个很好的理由来使用插入排序？

数值示例

让我们考虑以下两个函数：

• f(x) = 2x^2;这个函数有一个二次增长率，即”O(N^2)"
• g(x) = 10x;这个函数具有线性增长率，即”O(N)"

现在，让我们将两个函数绘制在一起：

^{来源：WolframAlpha：图 2x^2 和 10x 从 0 到 10 的 x}

请注意，在 、 之间，但对于任何较大的 ，很快就会长出来。x=0..5f(x) <= g(x)xf(x)g(x)

类似地，如果 A₁ 是开销较低的二次算法，而 A₂ 是开销较高的线性算法，则对于较小的输入，A₁ 可能比 A₂ 快。

因此，如果您选择这样做，您可以创建一个混合算法A₃，该算法仅根据输入的大小选择两种算法中的一种。这是否值得付出努力取决于所涉及的实际参数。

已经对排序算法进行了许多测试和比较，并且决定由于插入排序胜过小数组的合并排序，因此对于Arrays.sort实现两者都是值得的。

这是为了速度。mergeSort 的开销足够高，对于短数组，它比插入排序慢。