为什么java.util.Arrays.sort（Object []）使用2种排序算法？ [英] Why does java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms?

问题描述

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

伪代码：

  if（array.length <7）
 insertionSort ; 
 else 
 mergeSort（array）; 
  

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

解决方案

重要的是要注意一个算法 O（N log N） / code>在实践中不总是比 O（N ^ 2）算法更快。它取决于常量，以及涉及的 N 的范围。 （请记住，。

I found that java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms(in JDK 1.6).

pseudocode:

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

Why does it need 2 kinds of sorting here? for efficiency?

解决方案

It's important to note that an algorithm that is O(N log N) is not always faster in practice than an O(N^2) algorithm. It depends on the constants, and the range of N involved. (Remember that asymptotic notation measures relative growth rate, not absolute speed).

For small N, insertion sort in fact does beat merge sort. It's also faster for almost-sorted arrays.

Here's a quote:

Although it is one of the elementary sorting algorithms with O(N^2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

Here's another quote from Best sorting algorithm for nearly sorted lists paper:

straight insertion sort is best for small or very nearly sorted lists

What this means is that, in practice:

• Some algorithm A₁ with higher asymptotic upper bound may be preferable than another known algorithm A₂ with lower asymptotic upper bound
  • Perhaps A₂ is just too complicated to implement
  • Or perhaps it doesn't matter in the range of N considered
    • See e.g. Coppersmith–Winograd algorithm
• Some hybrid algorithms may adapt different algorithms depending on the input size

Related questions

• Which sorting algorithm is best suited to re-sort an almost fully sorted list?
• Is there ever a good reason to use Insertion Sort?

---

A numerical example

Let's consider these two functions:

• f(x) = 2x^2; this function has a quadratic growth rate, i.e. "O(N^2)"
• g(x) = 10x; this function has a linear growth rate, i.e. "O(N)"

Now let's plot the two functions together:

^{Source: WolframAlpha: plot 2x^2 and 10x for x from 0 to 10}

Note that between x=0..5, f(x) <= g(x), but for any larger x, f(x) quickly outgrows g(x).

Analogously, if A₁ is a quadratic algorithm with a low overhead, and A₂ is a linear algorithm with a high overhead, for smaller input, A₁ may be faster than A₂.

Thus, you can, should you choose to do so, create a hybrid algorithm A₃ which simply selects one of the two algorithms depending on the size of the input. Whether or not this is worth the effort depends on the actual parameters involved.

Many tests and comparisons of sorting algorithms have been made, and it was decided that because insertion sort beats merge sort for small arrays, it was worth it to implement both for Arrays.sort.

这篇关于为什么java.util.Arrays.sort（Object []）使用2种排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！