SakuraTears的博客

越努力越幸运

Java sort和parallelSort接口及其实现

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 15k 阅读时长 ≈ 14 分钟

前言

上篇文章我们介绍了 排序算法（九）-Java源码中的DualPivotQuicksort，今天我们来看下sort接口的实现，看看JDK对数据排序这块到底做了哪些优化。

正文

sort接口

sort接口有多个重载的方法，我们整理下后，它们分别如下：

在 java.util.Arrays类里，调用 Array.sort(a)方法，可以对数组a进行排序，它有18个重载方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//整个int数组排序
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
//对int数组from到to的位置进行排序
public static void sort(int[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//long数组
public static void sort(long[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(long[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//short数组
public static void sort(short[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(short[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//char数组
public static void sort(char[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(char[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//byte数组
public static void sort(byte[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1);
}
public static void sort(byte[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}

//float数组
public static void sort(float[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(float[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//double数组
public static void sort(double[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(double[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//Object数组
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a, fromIndex, toIndex);
    else
        ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

//泛型数组
public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
                            Comparator<? super T> c) {
    if (c == null) {
        sort(a, fromIndex, toIndex);
    } else {
        rangeCheck(a.length, fromIndex, toIndex);
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex, c);
        else
            TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
    }
}

源码分析

可以看到对于基本数据类型，因为排序稳定性不会对数据造成影响（两个一样的数据谁前谁后都可以），故使用了DualPivotQuicksort排序算法。

对于Object数组(没有继承Comparator接口的数据类型)，会先判断一个LegacyMergeSort.userRequested的值是否为真，如果为真就使用legacyMergeSort排序算法，否则就使用ComparableTimSort排序算法。

对于泛型数组T []，如果比较器Comparator为空，就按照Object []方式进行处理；如果有比较器的话，照样先判断LegacyMergeSort.userRequested的值是否为真，是的话就用legacyMergeSort排序算法，否则就使用TimSort排序算法。

其他地方的sort最终会调用Array.sort(a)方法。如java.util.Collections类里的sort(Listlist)方法，最终调用了Array.sort(T[] a)。

根据上面的分析，我们先来看看LegacyMergeSort.userRequested这个参数吧，因为它决定非基本数据类型数组到底是使用legacyMergeSort还是TimSort（ComparableTimSort是TimSort的Object []版本，也相当于TimSort）。

追踪源码，LegacyMergeSort.userRequested赋值过程如下：

1
2
3
4
5
6
static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

可以看到它是可以通过系统设置进行配置的，java -Djava.util.Arrays.useLegacyMergeSort=true，可以设置使用老的归并排序。

这个值默认是false，即不使用归并排序，Java之所以有这部分判断，完全是为了兼容老版本，同时归并排序这部分将在未来移除（当前介绍版本为JDK1.8，在JDK11中发现已经移除）。

legacyMergeSort这个方法涉及到的就是归并排序，关于这部分，我们不再展示源码（Java未来版本也会移除），有兴趣的可以看看我之前的文章归并排序(MergeSort)部分。这两者唯一不同的是Java的legacyMergeSort在排序部分长度小于 INSERTIONSORT_THRESHOLD = 7 的时候，会使用插入排序，相当于提高了普通归并的效率。

TimSort或者ComparableTimSort我在之前文章中也有分析了，有兴趣的可以看看，这儿不过多介绍。排序算法（六）- TimSort。

关于Java源码里的DualPivotQuicksort内容详见这篇文章排序算法（九）-Java源码中的DualPivotQuicksort。

parallelSort接口

看完串行排序接口，我们再来看下Java自带排序的并行版本parallelSort接口，看看它是如何实现并行排序的。

先看看它的几个重载方法,由于基本数据类型数组的parallelSort都是类似的，这儿我只拿int[]进行举例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//int数据并行排序方法（其它基本数据类型数组和其类似，这儿代码就不在展示）
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();
} 
public static void parallelSort(int[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    int n = toIndex - fromIndex, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJInt.Sorter
            (null, a, new int[n], fromIndex, n, 0,
                ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                MIN_ARRAY_SORT_GRAN : g).invoke();
}

//泛型数组并行排序方法（无比较器）
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();
}
public static <T extends Comparable<? super T>>
void parallelSort(T[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    int n = toIndex - fromIndex, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJObject.Sorter<T>
            (null, a,
                (T[])Array.newInstance(a.getClass().getComponentType(), n),
                fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}

//泛型数组并行排序方法（有比较器）
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
    if (cmp == null)
        cmp = NaturalOrder.INSTANCE;
    int n = a.length, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        TimSort.sort(a, 0, n, cmp, 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, cmp).invoke();
}
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
                                    Comparator<? super T> cmp) {
    rangeCheck(a.length, fromIndex, toIndex);
    if (cmp == null)
        cmp = NaturalOrder.INSTANCE;
    int n = toIndex - fromIndex, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJObject.Sorter<T>
            (null, a,
                (T[])Array.newInstance(a.getClass().getComponentType(), n),
                fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}

源码分析

对于基本类型数组数据，并行排序会判断排序长度n（或者数组长度）是否小于 MIN_ARRAY_SORT_GRAN = 1 << 13 = 8192，如果小于或者p = ForkJoinPool.getCommonPoolParallelism()) == 1的时候，就会使用DualPivotQuicksort排序算法；否则它创建了一个ArraysParallelSortHelpers.FJInt.Sorter类进行并行排序。

对于Object数组或者泛型数组T[]的排序，可以看到与基本数据类型相似，只是最后的排序算法使用的是稳定的TimSort，并行帮助类使用的是ArraysParallelSortHelpers.FJObject.Sorter，这个类底层串行排序也是基于TimSort。

我们来分析下并行排序源码：

对于长度小于8192很好理解，就是数据长度小的时候，使用串行排序就可以了，即DualPivotQuicksort，并没有使用并行排序。

而ForkJoinPool.getCommonPoolParallelism()是返回公共线程池的并行级别，即允许多少个线程并行，如果是1的话说明禁用了线程，那么就无法使用多线程，也就只能使用串行排序，关于这个值和ForkJoinPool相关，后面我们会看下这个类，来了解一下它的实现，这儿就不过多叙述。

我们重点来看下ArraysParallelSortHelpers.FJInt.Sorter这个类，这个是针对于int数组的并行工具类，当然我们还可以看到其它数据类型的并行工具类，如ArraysParallelSortHelpers.FJByte.Sorter，他们都在ArraysParallelSortHelpers这个类里。

这个类的并行实现是根据Cilk算法来实现的。

Cilk是一种多线程算法语言。Cilk背后的理念是，程序员应该集中精力构建程序，以暴露并行性和利用局部性，让Cilk的运行时系统负责调度计算，以便在给定平台上高效运行。因此，Cilk运行时系统负责诸如负载平衡、分页和通信协议等细节。然而，与其他多线程语言不同，Cilk是算法语言，因为运行时系统保证了高效和可预测的性能。

算法内容大致如下：

  1. 如果数组长度 n 过小（小于临界值 threshold ），就使用串行排序；

  2. 否则，将数组分为两半：

    • 将一半数组再分为两半（n/4），对于每一半，继续分割下去，直到数组长度小于临界值threshold，不再进行分割；
    • 对前一半串行排序，对后一半串行排序，两半排序是并行进行的；
    • 需要注意的是 n/2排序时需要保证两个n/4的并行排序合并完成，以此类推，n/4排序时需要保证两个n/8的并行排序合并完成……
    • 将两部分合并

其伪代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void parallelSort(int[] a,int low,int high){
    int n = high - low +1;
    if(n < threshold){
        sort(a);
    }else{
        int half = n >>>1;
        ForkJoinTaskTest task1 = ForkJoinTaskTest(a,low,half-1);
        task1.fork();
        ForkJoinTaskTest task2 = ForkJoinTaskTest(a,half,high-1);
        task2.compute();
        task1.join();
        merge(a,low,half,high-1);
    }
}

可以看到这个分割过程和我们之前说到过的 双调排序的并行版本有些许类似。

我们先不看Java源码的相关实现，我们想，如果我们自己实现一个并行版本的排序如何实现呢？

我们需要使用到ForkJoinPool，我们可以参考我的另一篇文章一道Java试题引发的思考。

这篇文章里使用了分支/合并框架（ForkJoinPool）来使用并行处理累加数据，我们参照这个模式，可以根据伪代码写出使用 Java DualPivotQuicksort的并行版本，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public class ParallelSort {
    public static void main(String[] args) throws Exception {
        int[] a = new int[100000000];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(100000000);
        }
        int[] b = a.clone();
        System.out.println("ParallelSort排序开始：");
        long start = System.currentTimeMillis();
        ForkJoinParallelSort task = new ForkJoinParallelSort(a);
        new ForkJoinPool().invoke(task);
        System.out.println("ParallelSort耗时：" + (System.currentTimeMillis() - start) + "ms");
        System.out.println("ParallelSort排序完成！");
        System.out.println("数组是否有序：" + isOrdered(a));

        System.out.println("ArrayParallelSort排序开始：");
        long start1 = System.currentTimeMillis();
        Arrays.parallelSort(b);
        System.out.println("ArrayParallelSort耗时：" + (System.currentTimeMillis() - start1) + "ms");
        System.out.println("ArrayParallelSort排序完成！");
        System.out.println("数组是否有序：" + isOrdered(b));
    }
}

class ForkJoinParallelSort extends RecursiveTask<Void> {
    /**
     * 要排序的数组
     */
    private final int[] array;
    /**
     * 数组起始下标
     */
    private final int start;
    /**
     * 数组结束下标
     */
    private final int end;
    /**
     * 数组最小长度
     */
    public static final int THRESHOLD = 8192;

    public ForkJoinParallelSort(int[] array) {
        this(array, 0, array.length - 1);
    }

    private ForkJoinParallelSort(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Void compute() {
        int length = end - start + 1;
        int half = length >>> 1;

        //小于等于阈值，串行排序处理
        if (length <= THRESHOLD) {
            computeSequentially(array, start, end);
            return null;
        }
        //创建一个子任务来为数组的前一半排序
        ForkJoinParallelSort leftTask = new ForkJoinParallelSort(array, start, start + half - 1);
        //利用另一个ForkJoinPool线程异步执行新创建的子任务
        leftTask.fork();
        //创建一个任务为数组的后一半排序
        ForkJoinParallelSort rightTask = new ForkJoinParallelSort(array, start + half, end);
        //同步执行第二个子任务，有可能允许进一步递归划分
        rightTask.compute();
        //读取第一个子任务的结果，没有完成就等待
        leftTask.join();
        //合并结果
        //long startTime = System.currentTimeMillis();
        merge(array, start, start + half - 1, start + half, end);
        //System.out.println("耗时："+(System.currentTimeMillis()-startTime)+"ms");
        return null;
    }
    /**
     * 使用JavaDualPivotQuickSort串行处理较小的数组
     *
     * @return
     */
    private void computeSequentially(int[] array, int start, int end) {
        //直接调用Arrays.sort 也可以
        JavaDualPivotQuicksort.sort(array, start, end, null, 0, 0);
    }
    /**
     * 快速合并两个有序数组   O(min(m,n))
     *
     * @param array
     * @param leftStart
     * @param leftEnd
     * @param rightStart
     * @param rightEnd
     */
    private void merge(int[] array, int leftStart, int leftEnd, int rightStart, int rightEnd) {
        if (array[leftEnd] <= array[rightStart]) {
            return;
        }
        int i = leftStart;
        int j = rightStart;
        int k = 0;
        int len1 = leftEnd - leftStart + 1;
        int len2 = rightEnd - rightStart + 1;
        int[] temp = new int[len1 + len2];
        while (i <= leftEnd && j <= rightEnd) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        if (i == leftEnd + 1 && j <= rightEnd) {
            System.arraycopy(array, j, temp, k, rightEnd - j + 1);
        }
        if (j == rightEnd + 1 && i <= leftEnd) {
            System.arraycopy(array, i, temp, k, leftEnd - i + 1);
        }
        //处理完后将temp赋值给array
        System.arraycopy(temp, 0, array, leftStart, len1);
        System.arraycopy(temp, len1, array, rightStart, len2);
    }
}

上述代码是比较好理解的，其要注意的地方是在排完序的两个有序数组合并上。

运行一下可以看到对于1亿数据量该方法耗时稳定在6-7s，Java源码的ParallelSort方法耗时在3-4s左右。

它们结果如下图：

upload successful

可以看到Java源码的排序处理速度要比我们实现的更高效的，速度差异主要在哪儿呢？

其实Java并行源码中借鉴了Cilk算法，但是有些不同的地方是，会把原数组分成四份进行并行排序。

算法说明如下：

  1. 将数组分成4个子数组。
  2. 对前面两个子数组进行排序然后合并。
  3. 对后面的两个进行排序然后合并。
    上面着几个步骤会重复递归，每个子数组都要求容量小于上面计算出来的临界值。

我们回到ArraysParallelSortHelpers这个类从它里面的FJInt这个类入手，其他的类的实现和其类似。

upload successful

upload successful

upload successful

根据上图的一些介绍，我再简单说明下。

其实上面图中Java源码这段代码是相当晦涩的，我们如何看出它每次是拆分成4个子任务并处理的呢？

我们可以根据第一次调用来看，这时候代码中的b = this.base = 0，wb = this.wbase = 0，则三个Sorter如下：

1
2
3
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();

代入b =0 可以看到，它们分别处理了[ u , u + n - u ],[ h , h + q ],[ q , q + h -q ] 三部分，正好是[ 3/4 , 1 ],[ 1/2 , 3/4 ],[ 1/4 , 1/2 ] 三部分。

而对于剩下的1/4 ，直接在当前线程处理（不需要fork），代码如下：

1
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);//注：此时 n = q （对于当前线程）,可以看源码的赋值过程

分别排序完了，需要进行合并，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
while (n > g) {
    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
    Relay fc = new Relay(new Merger(s, w, a, wb, h, wb+h, n-h, b, g));
    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,b+u, n-u, wb+h, g));
    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
    Relay bc = new Relay(new Merger(fc, a, w, b, q,b+q, h-q, wb, g));
    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
    s = new EmptyCompleter(bc);
    n = q;
}
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
s.tryComplete();

这段Relay的依存关系是 rc （合并后1/2部分）和 bc （合并前1/2部分） 是并行的，fc 会合并rc和bc （排序好的数据）。

Java中把并行分成四份的优势在哪里呢？

明显这段代码和使用我们Cilk算法每次分成两份的本质是一样的，而且分成4份代码变得更加晦涩。

具体原因就要说说这个Merger了，这个Merger是关于两个有序数组并行合并的实现，它的效率是非常高的，我们回到我们自己实现的那个ParallelSort类，可以看到我们设计的merge就是比较常规的合并，当两个数组数据量越大时，耗时越长，我在代码中注掉了耗时计算，有兴趣的童鞋可以打开观察下，在数据量较小情况下，其耗时基本是0~10ms，但是运行中随着两部分待合并的数据越来越大，耗时越来越大。

比如对于1亿数据的排序，其耗时主要消耗在2个5000w的数据合并成最终结果、4个2500w的数据两两合并成2个5000w数据、8个1250w的数据两两合并成4个2500w数据……的合并上。

Java中的这个Merger对合并进行了优化，使用了并行合并，其原理如下：

  1. 对于两个待合并数组A，B；
  2. 找到较大（或等于）的一个数组（比如A），如果长度小于阈值8192，就不分割了；如果大于8192，找到较大数组A的中点作为切割点M，使用二分法找到较小数组B中比这个切割点大的最小位置索引P；
  3. 这时候其实我们可以发现A中[lowA , M]和B中[lowB , P]位置数据合并后是始终 小于等于 A中[M , highA]和B中[P , highB]位置数据合并的，这就是分割合并有序的原则；
  4. 如果长度比较大，还会继续并行分割下去；
  5. 然后我们对上面拆分的数据两两合并，最终多线程执行完也就得到了有序数据。

有兴趣的童鞋可以参考原理结合上图看一下。

而我们在排序及合并时，会用到工作数组，分成4份后，可以保证最后的排序完成数组在原数组中，而不是在工作数组中，也避免了一次数据拷贝。

总结

关于Java自带排序的内容就介绍到这儿，可以看到相比于串行排序，并行排序更加复杂，但是Cilk并行算法的原理还是比较简单的，Java并排代码之所以复杂是因为它尽可能的优化了算法耗时。

这也是软件开发者应当具有的品质：精益求精。

源码

关于自写的ParallelSort排序可见于我的 GitHub。

关于 ArraysParallelSortHelpers相关代码可以参考JDK源码（1.8及以上版本）。

参考资料

  • JDK ArraysParallelSortHelpers源码
  • JDK Arrays源码



-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力！

欢迎关注我的其它发布渠道