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

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

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

## 最佳答案

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.

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.

• Some algorithm A1 with higher asymptotic upper bound may be preferable than another known algorithm A2 with lower asymptotic upper bound
• Perhaps A2 is just too complicated to implement
• Or perhaps it doesn't matter in the range of `N` considered
• Some hybrid algorithms may adapt different algorithms depending on the input size

### 相关问题

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

### 数值示例

• `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)`"

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

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`.