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

问题描述

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

伪代码：

  if（array.length  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:

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

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:

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种排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！