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

Question

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

伪代码：

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

为什么这里需要两种排序？是为了提高效率吗？

- 卢声远 Shengyuan Lu

Answer 1

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

对于小的 N，插入排序实际上比归并排序更快。对于几乎排序好的数组，它也更快。

下面是 一句引用:

尽管插入排序是具有最坏情况时间复杂度为 O(N^2) 的基本排序算法之一，但它是选择算法，因为数据几乎已经排序好了(因为它是自适应的)，或者问题规模很小(因为它的开销很低)。

出于这些原因，以及它也是稳定的，插入排序经常被用作递归基本情况(当问题规模很小时)的高开销分治排序算法的基础，例如归并排序或快速排序。

以下是来自 Best sorting algorithm for nearly sorted lists 论文的另一句引用:

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

这意味着，在实践中：

• 某些算法 A₁ 具有更高的渐进上界，可能比另一个已知算法 A₂ 具有更低的渐进上界更可取。
• 也许 A₂ 太复杂难以实现。
• 或者在考虑的范围内 N 的值没有关系。
  • 见例如Coppersmith–Winograd algorithm。
• 一些混合算法可以根据输入大小调整不同的算法。

相关问题

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

---

一个数值例子

让我们考虑这两个函数：

• 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实现两者。

- polygenelubricants

---

你或许想将上方的图表与我进行的插入排序和Java排序之间的一些实际测量进行比较。这是链接：http://www.javamex.com/tutorials/collections/sorting_java_algorithm_performance_2.shtml - Neil Coffey

除了这个优秀的分析之外，需要注意有两种不同类型的插入排序常用——一种是普通的插入排序，另一种是“二分插入排序”，它通过二分查找来找到要插入的位置，然后移动其他元素以腾出空间。在大多数处理器上，交换操作比比较操作更快，而二分插入排序可以减少比较次数。因此，在底层实现中通常会使用二分插入排序。 - Rex Kerr

Answer 2

这是为了速度考虑。由于归并排序的开销足够大，对于短数组而言，它比插入排序更慢。

- DJClayworth

Answer 3

引用自: http://zh.wikipedia.org/wiki/插入排序

Some divide-and-conquer algorithms such as quicksort and mergesort sort by 
recursively dividing the list into smaller sublists which are then sorted. 
A useful optimization in practice for these algorithms is to use insertion 
sort for sorting small sublists, where insertion sort outperforms these more 
complex algorithms. The size of list for which insertion sort has the advantage 
varies by environment and implementation, but is typically between eight and 
twenty elements.

- tszming

Answer 4

看起来他们认为对于短数组，mergeSort(array)速度较慢。希望他们确实进行了测试。

- ChrisH