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).
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
- See e.g. Coppersmith–Winograd algorithm
- 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. "
g(x) = 10x; this function has a linear growth rate, i.e. "
Note that between
f(x) <= g(x), but for any larger
f(x) quickly outgrows
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