对于原始数据类型 Primitive Type，Arrays.sort() 采用一种优化的快速排序算法
- 该排序算法是不稳定的，即：相等的两个元素在排序前后的相对位置可能会发生变化
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
对于引用数据类型 Object Type，Arrays.sort() 采用 Merge Sort 或者 Tim Sort
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
Arrays.parallelSort()
- 该排序算法是稳定的
- 只有当数组长度大于
MIN_ARRAY_SORT_GRAN 时才进行多线程并行排序 (源码中 MIN_ARRAY_SORT_GRAN 为 1<<13，即 8192)
- The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged.
- 将数组拆分成多个子数组，多线程进行排序，然后归并
public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
