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

Question

我发现java.util.Arrays.sort(Object[])使用2种排序算法(在JDK 1.6中).

伪代码:

if(array.length<7)
   insertionSort(array);
else
   mergeSort(array);

为什么这里需要2种排序？为了效率？

Answer 1

重要的是要注意一种算法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:plot 2x^2 and 10x for x from 0 to 10}

请注意,之间x=0..5,f(x) <= g(x)但是对于任何更大的x,f(x)快速生长g(x).

类似地,如果A ₁是具有低开销的二次算法,并且A ₂是具有高开销的线性算法,则对于较小的输入,A ₁可以比A ₂快.

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

已经对排序算法进行了许多测试和比较,并且决定因为插入排序对小型数组进行合并排序,所以实现两者都是值得的Arrays.sort.

Answer 2

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