在学习Fork/Join框架的时候，了解到Arrays.parallelSort()的底层实现用到了Fork/Join，所以看了一下这个方法的源码，记录一下自己的学习过程。

1
2
3
4
5
6
7
8
9
10
11
public static void parallelSort(int[] a) {
    int n = a.length, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJInt.Sorter
        (null, a, new int[n], 0, n, 0,
         ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
         MIN_ARRAY_SORT_GRAN : g).invoke();
}

MIN_ARRAY_SORT_GRAN这个是并行排序的阈值，如果大于这个值采用并行执行，并行用到了Fork/Join。

ForkJoinPool.getCommonPoolParallelism()这个方法的源码，这里看注释说明返回公共线程池的并行度，这里我追了一下源头，应该是根据电脑的CPU核数算出来的，暂时没深究。

1
2
3
4
5
6
7
8
9
/**
  * Returns the targeted parallelism level of the common pool.
  *
  * @return the targeted parallelism level of the common pool
  * @since 1.8
  */
public static int getCommonPoolParallelism() {
    return commonParallelism;
}

下面主要看一下DualPivotQuicksort.sort（双轴快速排序）这个方法的实现，

1
2
3
4
5
6
7
8
9
static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }
	...
}

这个地方判断如果排序的数量小于快速排序的阈值采用快速排序。然后看一下sort(a, left, right, true);这个方法，如果小于INSERTION_SORT_THRESHOLD用插入排序，这个方法不详细说了，了解一下Dual-Pivot Quicksort（新快速排序算法）

1
2
3
4
5
6
7
8
9
10
11
/**
  * Sorts the specified range of the array by Dual-Pivot Quicksort.
  *
  * @param a the array to be sorted
  * @param left the index of the first element, inclusive, to be sorted
  * @param right the index of the last element, inclusive, to be sorted
  * @param leftmost indicates if this part is the leftmost in the range
  */
private static void sort(int[] a, int left, int right, boolean leftmost) {
    int length = right - left + 1;
    if (length < INSERTION_SORT_THRESHOLD)