【Java】Arrays.sort:DualPivotQuicksort
一，概述
本文，笔者欲探索JDK内部排序算法实现，并记录心得。本文只解读DualPivotQuicksort，对于TimSort不在本文讨论范文。
其一，Arrrays.sort内部对于int[]、float[]、long[]、double[]等基本数组，使用的快排是双轴快排，它相对于普通快排，优化了最差的时间复杂度，毕竟在快排中，如果哨兵选择不当，时间复杂度会瞬间退回O(N^2)。
其二，Arrays内部对小数组排序优化，使用了插入排序，在小数组中更高效。
其三，Arrays支持ForkJoinTask多线程排序，使用parallelSort即可，并且给出了parallelSort高效临界阈值，低于此阈值不会开启多线程。
二，实现
以sort为入口，
内部调用DualPivotQuicksort，字义上即双哨兵快速排序
接下来，便是该算法实现了，
1，如果使用了parallelSort，且当size > MIN_PARALLEL_SORT_SIZE (4 << 10)，即2^12时，才会开启parallelism，否则效率会低于单线程排序。
2，调用sort方法，传入a、low、high，
跟进sort
传入bits = 0，暂且忽略mixedInsertSort和tryMergeRuns。
以上便是对小数组的排序优化，当size<MAX_INSERTION_SORT_SIZE(44)时，插入排序更加高效，
随后，便进入双轴快排两个哨兵的选取算法
1，选取step，是数组长度的八分之三 + 3，即 step = length&
2，从数组中取5个点，作为e1，e2，e3，e4，e5，
e3是整个数组中间值，e1,e5根据step选点，e2是e1和e3中间值，e4是e3和e5中间值，
e2大致在 ((3/8*size+3) + size / 2)/2位置，不赘述
3，根据e1,e2,e4,e5值，两两大小比较，交换值，最后满足e1<=e2<=e4<=e5
紧接着，e3也参与比较，最后满足e1<=e2<=e3<=e4<=e5
1，高位低位保留
2，当满足e1<e2<e3<e4<e5，即5个哨兵，值均不同时，则进入双轴快排算法分支，
3，两个哨兵取e1和e5，即选取5个点最小值与最大值，
1，将数组首位值赋值到e1，e5位置
2，从index1开始，找到第一个大于pivot1的下标，并记录为lower；
从index size-2开始，找到第一个小于pivot2的下标，并记录upper；
如此操作后，便划分了三个区域，如注释，
low~lower：值全部小于pivot1;
upder~end:值全部大于pivot2；
然后，使用第三个指针k，对lower~upper中间值进行扫描并交互，要求k~upper值满足
pivot1<=&&<=pivot2，直至k与lower重合，
再将哨兵返回到lower,upper位置，
如此以来，便得到一个新的序列，满足如下条件
e1，e5即选取的哨兵，e1<e5，lower\upper即哨兵点，
接下来，便是对low~lower，lower~upper，upper~end进行递归排序
以上即是对lower~upper，upper~end进行递归排序，而low~lower仍在本函数栈中继续进行，即将lower赋值给high（end = high - 1），别忘了，这个sort可是死循环函数。
这样，便能对三个区段再次递归排序，
如果无法满足e1<e2<e3<e4<e5，则进入单轴快排
单轴快排就不赘述了，此处，lower~upper == pivot
OK，关于Arrays.sort就讲到这里，下面顺带讲下多线程的sort算法，
三，ParallelSort
此算法是归并排序的多线程实现，根据depth判断是否使用sort函数，即不可分治区间时。
核心实现类是Sorter，间接集成ForkJoinTask，
compute中，当deptch > 0 时仍调用sort，对分治区域进行排序
depth来源以下算法
简单说，当排序序列size只有满足size>2^12，即分治终点是size < 2^12，便不再fork出更多的sorter了
onComplete中，便是归并，即Merger任务，同样也是继承ForkJoinTask，不赘述
