2  * Copyright (c) 2009, 2016, Oracle and/or its affiliates. All rights reserved.

     2  * Copyright (c) 2009, 2019, Oracle and/or its affiliates. All rights reserved.

    29  * This class implements the Dual-Pivot Quicksort algorithm by

    32  * This class implements powerful and fully optimized versions, both

    30  * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm

    33  * sequential and parallel, of the Dual-Pivot Quicksort algorithm by

    31  * offers O(n log(n)) performance on many data sets that cause other

    34  * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

    32  * quicksorts to degrade to quadratic performance, and is typically

    35  * offers O(n log(n)) performance on all data sets, and is typically

    35  * All exposed methods are package-private, designed to be invoked

    38  * There are also additional algorithms, invoked from the Dual-Pivot

    36  * from public methods (in class Arrays) after performing any

    39  * Quicksort, such as mixed insertion sort, merging of runs and heap

    37  * necessary array bounds checks and expanding parameters into the

    40  * sort, counting sort and parallel merge sort.

    38  * required forms.

    44  * @version 2011.02.11 m765.827.12i:5\7pm

    47  * @version 2018.08.18

    45  * @since 1.7

    48  *

    49  * @since 1.7 * 14

    54     /*

    58     /**

    55      * Tuning parameters.

    59      * Max array size to use mixed insertion sort.

    56      */

    60      */

    57 

    61     private static final int MAX_MIXED_INSERTION_SORT_SIZE = 65;

    58     /**

    62 

    59      * The maximum number of runs in merge sort.

    63     /**

    60      */

    64      * Max array size to use insertion sort.

    61     private static final int MAX_RUN_COUNT = 67;

    65      */

    62 

    66     private static final int MAX_INSERTION_SORT_SIZE = 44;

    63     /**

    67 

    64      * If the length of an array to be sorted is less than this

    68     /**

    65      * constant, Quicksort is used in preference to merge sort.

    69      * Min array size to perform sorting in parallel.

    66      */

    70      */

    67     private static final int QUICKSORT_THRESHOLD = 286;

    71     private static final int MIN_PARALLEL_SORT_SIZE = 4 << 10;

    68 

    72 

    69     /**

    73     /**

    70      * If the length of an array to be sorted is less than this

    74      * Min array size to try merging of runs.

    71      * constant, insertion sort is used in preference to Quicksort.

    75      */

    72      */

    76     private static final int MIN_TRY_MERGE_SIZE = 4 << 10;

    73     private static final int INSERTION_SORT_THRESHOLD = 47;

    77 

    74 

    78     /**

    75     /**

    79      * Min size of the first run to continue with scanning.

    76      * If the length of a byte array to be sorted is greater than this

    80      */

    77      * constant, counting sort is used in preference to insertion sort.

    81     private static final int MIN_FIRST_RUN_SIZE = 16;

    78      */

    82 

    79     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

    83     /**

    80 

    84      * Min factor for the first runs to continue scanning.

    81     /**

    85      */

    82      * If the length of a short or char array to be sorted is greater

    86     private static final int MIN_FIRST_RUNS_FACTOR = 7;

    83      * than this constant, counting sort is used in preference to Quicksort.

    87 

    84      */

    88     /**

    85     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

    89      * Max capacity of the index array for tracking runs.

    86 

    90      */

    87     /*

    91     private static final int MAX_RUN_CAPACITY = 5 << 10;

    88      * Sorting methods for seven primitive types.

    92 

    89      */

    93     /**

    90 

    94      * Min number of runs, required by parallel merging.

    91     /**

    95      */

    92      * Sorts the specified range of the array using the given

    96     private static final int MIN_RUN_COUNT = 4;

    93      * workspace array slice if possible for merging

    97 

    98     /**

    99      * Min array size to use parallel merging of parts.

   100      */

   101     private static final int MIN_PARALLEL_MERGE_PARTS_SIZE = 4 << 10;

   102 

   103     /**

   104      * Min size of a byte array to use counting sort.

   105      */

   106     private static final int MIN_BYTE_COUNTING_SORT_SIZE = 64;

   107 

   108     /**

   109      * Min size of a short or char array to use counting sort.

   110      */

   111     private static final int MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE = 1750;

   112 

   113     /**

   114      * Threshold of mixed insertion sort is incremented by this value.

   115      */

   116     private static final int DELTA = 3 << 1;

   117 

   118     /**

   119      * Max recursive partitioning depth before using heap sort.

   120      */

   121     private static final int MAX_RECURSION_DEPTH = 64 * DELTA;

   122 

   123     /**

   124      * Calculates the double depth of parallel merging.

   125      * Depth is negative, if tasks split before sorting.

   126      *

   127      * @param parallelism the parallelism level

   128      * @param size the target size

   129      * @return the depth of parallel merging

   130      */

   131     private static int getDepth(int parallelism, int size) {

   132         int depth = 0;

   133 

   134         while ((parallelism >>= 3) > 0 && (size >>= 2) > 0) {

   135             depth -= 2;

   136         }

   137         return depth;

   138     }

   139 

   140     /**

   141      * Sorts the specified range of the array using parallel merge

   142      * sort and/or Dual-Pivot Quicksort.

   143      *

   144      * To balance the faster splitting and parallelism of merge sort

   145      * with the faster element partitioning of Quicksort, ranges are

   146      * subdivided in tiers such that, if there is enough parallelism,

   147      * the four-way parallel merge is started, still ensuring enough

   148      * parallelism to process the partitions.

    96      * @param left the index of the first element, inclusive, to be sorted

   151      * @param parallelism the parallelism level

    97      * @param right the index of the last element, inclusive, to be sorted

   152      * @param low the index of the first element, inclusive, to be sorted

    98      * @param work a workspace array (slice)

   153      * @param high the index of the last element, exclusive, to be sorted

    99      * @param workBase origin of usable space in work array

   154      */

   100      * @param workLen usable size of work array

   155     static void sort(int[] a, int parallelism, int low, int high) {

   101      */

   156         int size = high - low;

   102     static void sort(int[] a, int left, int right,

   157 

   103                      int[] work, int workBase, int workLen) {

   158         if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {

   104         // Use Quicksort on small arrays

   159             int depth = getDepth(parallelism, size >> 12);

   105         if (right - left < QUICKSORT_THRESHOLD) {

   160             int[] b = depth == 0 ? null : new int[size];

   106             sort(a, left, right, true);

   161             new Sorter(null, a, b, low, size, low, depth).invoke();

   107             return;

   162         } else {

   108         }

   163             sort(null, a, 0, low, high);

   109 

   164         }

   110         /*

   165     }

   111          * Index run[i] is the start of i-th run

   166 

   112          * (ascending or descending sequence).

   167     /**

   113          */

   168      * Sorts the specified array using the Dual-Pivot Quicksort and/or

   114         int[] run = new int[MAX_RUN_COUNT + 1];

   169      * other sorts in special-cases, possibly with parallel partitions.

   115         int count = 0; run[0] = left;

   170      *

   116 

   171      * @param sorter parallel context

   117         // Check if the array is nearly sorted

   172      * @param a the array to be sorted

   118         for (int k = left; k < right; run[count] = k) {

   173      * @param bits the combination of recursion depth and bit flag, where

   119             // Equal items in the beginning of the sequence

   174      *        the right bit "0" indicates that array is the leftmost part

   120             while (k < right && a[k] == a[k + 1])

   175      * @param low the index of the first element, inclusive, to be sorted

   121                 k++;

   176      * @param high the index of the last element, exclusive, to be sorted

   122             if (k == right) break;  // Sequence finishes with equal items

   177      */

   123             if (a[k] < a[k + 1]) { // ascending

   178     static void sort(Sorter sorter, int[] a, int bits, int low, int high) {

   124                 while (++k <= right && a[k - 1] <= a[k]);

   179         while (true) {

   125             } else if (a[k] > a[k + 1]) { // descending

   180             int end = high - 1, size = high - low;

   126                 while (++k <= right && a[k - 1] >= a[k]);

   181 

   127                 // Transform into an ascending sequence

   182             /*

   128                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {

   183              * Run mixed insertion sort on small non-leftmost parts.

   129                     int t = a[lo]; a[lo] = a[hi]; a[hi] = t;

   184              */

   130                 }

   185             if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {

   131             }

   186                 mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);

   132 

   133             // Merge a transformed descending sequence followed by an

   134             // ascending sequence

   135             if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {

   136                 count--;

   137             }

   138 

   139             /*

   140              * The array is not highly structured,

   141              * use Quicksort instead of merge sort.

   142              */

   143             if (++count == MAX_RUN_COUNT) {

   144                 sort(a, left, right, true);

   147         }

   189 

   148 

   190             /*

   149         // These invariants should hold true:

   191              * Invoke insertion sort on small leftmost part.

   150         //    run[0] = 0

   192              */

   151         //    run[<last>] = right + 1; (terminator)

   193             if (size < MAX_INSERTION_SORT_SIZE) {

   152 

   194                 insertionSort(a, low, high);

   153         if (count == 0) {

   195                 return;

   154             // A single equal run

   196             }

   155             return;

   197 

   156         } else if (count == 1 && run[count] > right) {

   198             /*

   157             // Either a single ascending or a transformed descending run.

   199              * Check if the whole array or large non-leftmost

   158             // Always check that a final run is a proper terminator, otherwise

   200              * parts are nearly sorted and then merge runs.

   159             // we have an unterminated trailing run, to handle downstream.

   201              */

   160             return;

   202             if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)

   161         }

   203                     && tryMergeRuns(sorter, a, low, size)) {

   162         right++;

   204                 return;

   163         if (run[count] < right) {

   205             }

   164             // Corner case: the final run is not a terminator. This may happen

   206 

   165             // if a final run is an equals run, or there is a single-element run

   207             /*

   166             // at the end. Fix up by adding a proper terminator at the end.

   208              * Switch to heap sort if execution

   167             // Note that we terminate with (right + 1), incremented earlier.

   209              * time is becoming quadratic.

   168             run[++count] = right;

   210              */

   169         }

   211             if ((bits += DELTA) > MAX_RECURSION_DEPTH) {

   170 

   212                 heapSort(a, low, high);

   171         // Determine alternation base for merge

   213                 return;

   172         byte odd = 0;

   214             }

   173         for (int n = 1; (n <<= 1) < count; odd ^= 1);

   215 

   174 

   216             /*

   175         // Use or create temporary array b for merging

   217              * Use an inexpensive approximation of the golden ratio

   176         int[] b;                 // temp array; alternates with a

   218              * to select five sample elements and determine pivots.

   177         int ao, bo;              // array offsets from 'left'

   219              */

   178         int blen = right - left; // space needed for b

   220             int step = (size >> 3) * 3 + 3;

   179         if (work == null || workLen < blen || workBase + blen > work.length) {

   221 

   180             work = new int[blen];

   222             /*

   181             workBase = 0;

   223              * Five elements around (and including) the central element

   182         }

   224              * will be used for pivot selection as described below. The

   183         if (odd == 0) {

   225              * unequal choice of spacing these elements was empirically

   184             System.arraycopy(a, left, work, workBase, blen);

   226              * determined to work well on a wide variety of inputs.

   185             b = a;

   227              */

   186             bo = 0;

   228             int e1 = low + step;

   187             a = work;

   229             int e5 = end - step;

   188             ao = workBase - left;

   230             int e3 = (e1 + e5) >>> 1;

   189         } else {

   231             int e2 = (e1 + e3) >>> 1;

   190             b = work;

   232             int e4 = (e3 + e5) >>> 1;

   191             ao = 0;

   233             int a3 = a[e3];

   192             bo = workBase - left;

   234 

   193         }

   235             /*

   194 

   236              * Sort these elements in place by the combination

   195         // Merging

   237              * of 4-element sorting network and insertion sort.

   196         for (int last; count > 1; count = last) {

   197             for (int k = (last = 0) + 2; k <= count; k += 2) {

   198                 int hi = run[k], mi = run[k - 1];

   199                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {

   200                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {

   201                         b[i + bo] = a[p++ + ao];

   202                     } else {

   203                         b[i + bo] = a[q++ + ao];

   204                     }

   205                 }

   206                 run[++last] = hi;

   207             }

   208             if ((count & 1) != 0) {

   209                 for (int i = right, lo = run[count - 1]; --i >= lo;

   210                     b[i + bo] = a[i + ao]

   211                 );

   212                 run[++last] = right;

   213             }

   214             int[] t = a; a = b; b = t;

   215             int o = ao; ao = bo; bo = o;

   216         }

   217     }

   218 

   219     /**

   220      * Sorts the specified range of the array by Dual-Pivot Quicksort.

   221      *

   222      * @param a the array to be sorted

   223      * @param left the index of the first element, inclusive, to be sorted

   224      * @param right the index of the last element, inclusive, to be sorted

   225      * @param leftmost indicates if this part is the leftmost in the range

   226      */

   227     private static void sort(int[] a, int left, int right, boolean leftmost) {

   228         int length = right - left + 1;

   229 

   230         // Use insertion sort on tiny arrays

   231         if (length < INSERTION_SORT_THRESHOLD) {

   232             if (leftmost) {

   233                 /*

   234                  * Traditional (without sentinel) insertion sort,

   235                  * optimized for server VM, is used in case of

   236                  * the leftmost part.

   237                  */

   238                 for (int i = left, j = i; i < right; j = ++i) {

   239                     int ai = a[i + 1];

   240                     while (ai < a[j]) {

   241                         a[j + 1] = a[j];

   242                         if (j-- == left) {

   243                             break;

   244                         }

   245                     }

   246                     a[j + 1] = ai;

   247                 }

   248             } else {

   249                 /*

   250                  * Skip the longest ascending sequence.

   251                  */

   252                 do {

   253                     if (left >= right) {

   254                         return;

   255                     }

   256                 } while (a[++left] >= a[left - 1]);

   257 

   258                 /*

   259                  * Every element from adjoining part plays the role

   260                  * of sentinel, therefore this allows us to avoid the

   261                  * left range check on each iteration. Moreover, we use

   262                  * the more optimized algorithm, so called pair insertion

   263                  * sort, which is faster (in the context of Quicksort)

   264                  * than traditional implementation of insertion sort.

   265                  */

   266                 for (int k = left; ++left <= right; k = ++left) {

   267                     int a1 = a[k], a2 = a[left];

   268 

   269                     if (a1 < a2) {

   270                         a2 = a1; a1 = a[left];

   271                     }

   272                     while (a1 < a[--k]) {

   273                         a[k + 2] = a[k];

   274                     }

   275                     a[++k + 1] = a1;

   276 

   277                     while (a2 < a[--k]) {

   278                         a[k + 1] = a[k];

   279                     }

   280                     a[k + 1] = a2;

   281                 }

   282                 int last = a[right];

   283 

   284                 while (last < a[--right]) {

   285                     a[right + 1] = a[right];

   286                 }

   287                 a[right + 1] = last;

   288             }

   289             return;

   290         }

   291 

   292         // Inexpensive approximation of length / 7

   293         int seventh = (length >> 3) + (length >> 6) + 1;

   294 

   295         /*

   296          * Sort five evenly spaced elements around (and including) the

   297          * center element in the range. These elements will be used for

   298          * pivot selection as described below. The choice for spacing

   299          * these elements was empirically determined to work well on

   300          * a wide variety of inputs.

   301          */

   302         int e3 = (left + right) >>> 1; // The midpoint

   303         int e2 = e3 - seventh;

   304         int e1 = e2 - seventh;

   305         int e4 = e3 + seventh;

   306         int e5 = e4 + seventh;

   307 

   308         // Sort these elements using insertion sort

   309         if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

   310 

   311         if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;

   312             if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }

   313         }

   314         if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;

   315             if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;

   316                 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }

   317             }

   318         }

   319         if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;

   320             if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;

   321                 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;

   322                     if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }

   323                 }

   324             }

   325         }

   326 

   327         // Pointers

   328         int less  = left;  // The index of the first element of center part

   329         int great = right; // The index before the first element of right part

   330 

   331         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {

   332             /*

   333              * Use the second and fourth of the five sorted elements as pivots.

   334              * These values are inexpensive approximations of the first and

   335              * second terciles of the array. Note that pivot1 <= pivot2.

   336              */

   337             int pivot1 = a[e2];

   338             int pivot2 = a[e4];

   339 

   340             /*

   341              * The first and the last elements to be sorted are moved to the

   342              * locations formerly occupied by the pivots. When partitioning

   343              * is complete, the pivots are swapped back into their final

   344              * positions, and excluded from subsequent sorting.

   345              */

   346             a[e2] = a[left];

   347             a[e4] = a[right];

   348 

   349             /*

   350              * Skip elements, which are less or greater than pivot values.

   351              */

   352             while (a[++less] < pivot1);

   353             while (a[--great] > pivot2);

   354 

   355             /*

   356              * Partitioning:

   358              *   left part           center part                   right part

   239              *    5 ------o-----------o------------

   359              * +--------------------------------------------------------------+

   240              *            |           |

   360              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |

   241              *    4 ------|-----o-----o-----o------

   361              * +--------------------------------------------------------------+

   242              *            |     |           |

   362              *               ^                          ^       ^

   243              *    2 ------o-----|-----o-----o------

   363              *               |                          |       |

   244              *                  |     |

   364              *              less                        k     great

   245              *    1 ------------o-----o------------

   365              *

   246              */

   366              * Invariants:

   247             if (a[e5] < a[e2]) { int t = a[e5]; a[e5] = a[e2]; a[e2] = t; }

   367              *

   248             if (a[e4] < a[e1]) { int t = a[e4]; a[e4] = a[e1]; a[e1] = t; }

   368              *              all in (left, less)   < pivot1

   249             if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; }

   369              *    pivot1 <= all in [less, k)     <= pivot2

   250             if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

   370              *              all in (great, right) > pivot2

   251             if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; }

   371              *

   252 

   372              * Pointer k is the first index of ?-part.

   253             if (a3 < a[e2]) {

   373              */

   254                 if (a3 < a[e1]) {

   374             outer:

   255                     a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;

   375             for (int k = less - 1; ++k <= great; ) {

   256                 } else {

   376                 int ak = a[k];

   257                     a[e3] = a[e2]; a[e2] = a3;

   377                 if (ak < pivot1) { // Move a[k] to left part

   258                 }

   378                     a[k] = a[less];

   259             } else if (a3 > a[e4]) {

   379                     /*

   260                 if (a3 > a[e5]) {

   380                      * Here and below we use "a[i] = b; i++;" instead

   261                     a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;

   381                      * of "a[i++] = b;" due to performance issue.

   262                 } else {

   382                      */

   263                     a[e3] = a[e4]; a[e4] = a3;

   383                     a[less] = ak;

   264                 }

   384                     ++less;

   265             }

   385                 } else if (ak > pivot2) { // Move a[k] to right part

   266 

   386                     while (a[great] > pivot2) {

   267             // Pointers

   387                         if (great-- == k) {

   268             int lower = low; // The index of the last element of the left part

   388                             break outer;

   269             int upper = end; // The index of the first element of the right part

   389                         }

   270 

   390                     }

   271             /*

   391                     if (a[great] < pivot1) { // a[great] <= pivot2

   272              * Partitioning with 2 pivots in case of different elements.

   392                         a[k] = a[less];

   273              */

   393                         a[less] = a[great];

   274             if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {

   394                         ++less;

   275 

   395                     } else { // pivot1 <= a[great] <= pivot2

   276                 /*

   396                         a[k] = a[great];

   277                  * Use the first and fifth of the five sorted elements as

   397                     }

   278                  * the pivots. These values are inexpensive approximation

   398                     /*

   279                  * of tertiles. Note, that pivot1 < pivot2.

   399                      * Here and below we use "a[i] = b; i--;" instead

   280                  */

   400                      * of "a[i--] = b;" due to performance issue.

   281                 int pivot1 = a[e1];

   401                      */

   282                 int pivot2 = a[e5];

   402                     a[great] = ak;

   283 

   403                     --great;

   284                 /*

   404                 }

   285                  * The first and the last elements to be sorted are moved

   405             }

   286                  * to the locations formerly occupied by the pivots. When

   406 

   287                  * partitioning is completed, the pivots are swapped back

   407             // Swap pivots into their final positions

   288                  * into their final positions, and excluded from the next

   408             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;

   289                  * subsequent sorting.

   409             a[right] = a[great + 1]; a[great + 1] = pivot2;

   290                  */

   410 

   291                 a[e1] = a[lower];

   411             // Sort left and right parts recursively, excluding known pivots

   292                 a[e5] = a[upper];

   412             sort(a, left, less - 2, leftmost);

   293 

   413             sort(a, great + 2, right, false);

   294                 /*

   414 

   295                  * Skip elements, which are less or greater than the pivots.

   415             /*

   296                  */

   416              * If center part is too large (comprises > 4/7 of the array),

   297                 while (a[++lower] < pivot1);

   417              * swap internal pivot values to ends.

   298                 while (a[--upper] > pivot2);

   418              */

   299 

   419             if (less < e1 && e5 < great) {

   300                 /*

   420                 /*

   301                  * Backward 3-interval partitioning

   421                  * Skip elements, which are equal to pivot values.

   302                  *

   422                  */

   303                  *   left part                 central part          right part

   423                 while (a[less] == pivot1) {

   304                  * +------------------------------------------------------------+

   424                     ++less;

   305                  * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |

   425                 }

   306                  * +------------------------------------------------------------+

   426 

   307                  *             ^       ^                            ^

   427                 while (a[great] == pivot2) {

   308                  *             |       |                            |

   428                     --great;

   309                  *           lower     k                          upper

   429                 }

   430 

   431                 /*

   432                  * Partitioning:

   433                  *

   434                  *   left part         center part                  right part

   435                  * +----------------------------------------------------------+

   436                  * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |

   437                  * +----------------------------------------------------------+

   438                  *              ^                        ^       ^

   439                  *              |                        |       |

   440                  *             less                      k     great

   444                  *              all in (*,  less) == pivot1

   313                  *              all in (low, lower] < pivot1

   445                  *     pivot1 < all in [less,  k)  < pivot2

   314                  *    pivot1 <= all in (k, upper)  <= pivot2

   446                  *              all in (great, *) == pivot2

   315                  *              all in [upper, end) > pivot2

   447                  *

   316                  *

   448                  * Pointer k is the first index of ?-part.

   317                  * Pointer k is the last index of ?-part

   449                  */

   318                  */

   450                 outer:

   319                 for (int unused = --lower, k = ++upper; --k > lower; ) {

   451                 for (int k = less - 1; ++k <= great; ) {

   453                     if (ak == pivot1) { // Move a[k] to left part

   321 

   454                         a[k] = a[less];

   322                     if (ak < pivot1) { // Move a[k] to the left side

   455                         a[less] = ak;

   323                         while (lower < k) {

   456                         ++less;

   324                             if (a[++lower] >= pivot1) {

   457                     } else if (ak == pivot2) { // Move a[k] to right part

   325                                 if (a[lower] > pivot2) {

   458                         while (a[great] == pivot2) {

   326                                     a[k] = a[--upper];

   459                             if (great-- == k) {

   327                                     a[upper] = a[lower];

   460                                 break outer;

   328                                 } else {

   329                                     a[k] = a[lower];

   330                                 }

   331                                 a[lower] = ak;

   332                                 break;

   463                         if (a[great] == pivot1) { // a[great] < pivot2

   335                     } else if (ak > pivot2) { // Move a[k] to the right side

   464                             a[k] = a[less];

   336                         a[k] = a[--upper];

   465                             /*

   337                         a[upper] = ak;

   466                              * Even though a[great] equals to pivot1, the

   338                     }

   467                              * assignment a[less] = pivot1 may be incorrect,

   339                 }

   468                              * if a[great] and pivot1 are floating-point zeros

   340 

   469                              * of different signs. Therefore in float and

   341                 /*

   470                              * double sorting methods we have to use more

   342                  * Swap the pivots into their final positions.

   471                              * accurate assignment a[less] = a[great].

   343                  */

   472                              */

   344                 a[low] = a[lower]; a[lower] = pivot1;

   473                             a[less] = pivot1;

   345                 a[end] = a[upper]; a[upper] = pivot2;

   474                             ++less;

   346 

   475                         } else { // pivot1 < a[great] < pivot2

   347                 /*

   476                             a[k] = a[great];

   348                  * Sort non-left parts recursively (possibly in parallel),

   349                  * excluding known pivots.

   350                  */

   351                 if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {

   352                     sorter.forkSorter(bits | 1, lower + 1, upper);

   353                     sorter.forkSorter(bits | 1, upper + 1, high);

   354                 } else {

   355                     sort(sorter, a, bits | 1, lower + 1, upper);

   356                     sort(sorter, a, bits | 1, upper + 1, high);

   357                 }

   358 

   359             } else { // Use single pivot in case of many equal elements

   360 

   361                 /*

   362                  * Use the third of the five sorted elements as the pivot.

   363                  * This value is inexpensive approximation of the median.

   364                  */

   365                 int pivot = a[e3];

   366 

   367                 /*

   368                  * The first element to be sorted is moved to the

   369                  * location formerly occupied by the pivot. After

   370                  * completion of partitioning the pivot is swapped

   371                  * back into its final position, and excluded from

   372                  * the next subsequent sorting.

   373                  */

   374                 a[e3] = a[lower];

   375 

   376                 /*

   377                  * Traditional 3-way (Dutch National Flag) partitioning

   378                  *

   379                  *   left part                 central part    right part

   380                  * +------------------------------------------------------+

   381                  * |   < pivot   |     ?     |   == pivot   |   > pivot   |

   382                  * +------------------------------------------------------+

   383                  *              ^           ^                ^

   384                  *              |           |                |

   385                  *            lower         k              upper

   386                  *

   387                  * Invariants:

   388                  *

   389                  *   all in (low, lower] < pivot

   390                  *   all in (k, upper)  == pivot

   391                  *   all in [upper, end] > pivot

   392                  *

   393                  * Pointer k is the last index of ?-part

   394                  */

   395                 for (int k = ++upper; --k > lower; ) {

   396                     int ak = a[k];

   397 

   398                     if (ak != pivot) {

   399                         a[k] = pivot;

   400 

   401                         if (ak < pivot) { // Move a[k] to the left side

   402                             while (a[++lower] < pivot);

   403 

   404                             if (a[lower] > pivot) {

   405                                 a[--upper] = a[lower];

   406                             }

   407                             a[lower] = ak;

   408                         } else { // ak > pivot - Move a[k] to the right side

   409                             a[--upper] = ak;

   478                         a[great] = ak;

   411                     }

   479                         --great;

   412                 }

   480                     }

   413 

   481                 }

   414                 /*

   482             }

   415                  * Swap the pivot into its final position.

   483 

   416                  */

   484             // Sort center part recursively

   417                 a[low] = a[lower]; a[lower] = pivot;

   485             sort(a, less, great, false);

   418 

   486 

   419                 /*

   487         } else { // Partitioning with one pivot

   420                  * Sort the right part (possibly in parallel), excluding

   488             /*

   421                  * known pivot. All elements from the central part are

   489              * Use the third of the five sorted elements as pivot.

   422                  * equal and therefore already sorted.

   490              * This value is inexpensive approximation of the median.

   423                  */

   491              */

   424                 if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {

   492             int pivot = a[e3];

   425                     sorter.forkSorter(bits | 1, upper, high);

   493 

   426                 } else {

   494             /*

   427                     sort(sorter, a, bits | 1, upper, high);

   495              * Partitioning degenerates to the traditional 3-way

   428                 }

   496              * (or "Dutch National Flag") schema:

   429             }

   430             high = lower; // Iterate along the left part

   431         }

   432     }

   433 

   434     /**

   435      * Sorts the specified range of the array using mixed insertion sort.

   436      *

   437      * Mixed insertion sort is combination of simple insertion sort,

   438      * pin insertion sort and pair insertion sort.

   439      *

   440      * In the context of Dual-Pivot Quicksort, the pivot element

   441      * from the left part plays the role of sentinel, because it

   442      * is less than any elements from the given part. Therefore,

   443      * expensive check of the left range can be skipped on each

   444      * iteration unless it is the leftmost call.

   445      *

   446      * @param a the array to be sorted

   447      * @param low the index of the first element, inclusive, to be sorted

   448      * @param end the index of the last element for simple insertion sort

   449      * @param high the index of the last element, exclusive, to be sorted

   450      */

   451     private static void mixedInsertionSort(int[] a, int low, int end, int high) {

   452         if (end == high) {

   453 

   454             /*

   455              * Invoke simple insertion sort on tiny array.

   456              */

   457             for (int i; ++low < end; ) {

   458                 int ai = a[i = low];

   459 

   460                 while (ai < a[--i]) {

   461                     a[i + 1] = a[i];

   462                 }

   463                 a[i + 1] = ai;

   464             }

   465         } else {

   466 

   467             /*

   468              * Start with pin insertion sort on small part.

   498              *   left part    center part              right part

   470              * Pin insertion sort is extended simple insertion sort.

   499              * +-------------------------------------------------+

   471              * The main idea of this sort is to put elements larger

   500              * |  < pivot  |   == pivot   |     ?    |  > pivot  |

   472              * than an element called pin to the end of array (the

   501              * +-------------------------------------------------+

   473              * proper area for such elements). It avoids expensive

   502              *              ^              ^        ^

   474              * movements of these elements through the whole array.

   503              *              |              |        |

   475              */

   504              *             less            k      great

   476             int pin = a[end];

   477 

   478             for (int i, p = high; ++low < end; ) {

   479                 int ai = a[i = low];

   480 

   481                 if (ai < a[i - 1]) { // Small element

   482 

   483                     /*

   484                      * Insert small element into sorted part.

   485                      */

   486                     a[i] = a[--i];

   487 

   488                     while (ai < a[--i]) {

   489                         a[i + 1] = a[i];

   490                     }

   491                     a[i + 1] = ai;

   492 

   493                 } else if (p > i && ai > pin) { // Large element

   494 

   495                     /*

   496                      * Find element smaller than pin.

   497                      */

   498                     while (a[--p] > pin);

   499 

   500                     /*

   501                      * Swap it with large element.

   502                      */

   503                     if (p > i) {

   504                         ai = a[p];

   505                         a[p] = a[i];

   506                     }

   507 

   508                     /*

   509                      * Insert small element into sorted part.

   510                      */

   511                     while (ai < a[--i]) {

   512                         a[i + 1] = a[i];

   513                     }

   514                     a[i + 1] = ai;

   515                 }

   516             }

   517 

   518             /*

   519              * Continue with pair insertion sort on remain part.

   520              */

   521             for (int i; low < high; ++low) {

   522                 int a1 = a[i = low], a2 = a[++low];

   523 

   524                 /*

   525                  * Insert two elements per iteration: at first, insert the

   526                  * larger element and then insert the smaller element, but

   527                  * from the position where the larger element was inserted.

   528                  */

   529                 if (a1 > a2) {

   530 

   531                     while (a1 < a[--i]) {

   532                         a[i + 2] = a[i];

   533                     }

   534                     a[++i + 1] = a1;

   535 

   536                     while (a2 < a[--i]) {

   537                         a[i + 1] = a[i];

   538                     }

   539                     a[i + 1] = a2;

   540 

   541                 } else if (a1 < a[i - 1]) {

   542 

   543                     while (a2 < a[--i]) {

   544                         a[i + 2] = a[i];

   545                     }

   546                     a[++i + 1] = a2;

   547 

   548                     while (a1 < a[--i]) {

   549                         a[i + 1] = a[i];

   550                     }

   551                     a[i + 1] = a1;

   552                 }

   553             }

   554         }

   555     }

   556 

   557     /**

   558      * Sorts the specified range of the array using insertion sort.

   559      *

   560      * @param a the array to be sorted

   561      * @param low the index of the first element, inclusive, to be sorted

   562      * @param high the index of the last element, exclusive, to be sorted

   563      */

   564     private static void insertionSort(int[] a, int low, int high) {

   565         for (int i, k = low; ++k < high; ) {

   566             int ai = a[i = k];

   567 

   568             if (ai < a[i - 1]) {

   569                 while (--i >= low && ai < a[i]) {

   570                     a[i + 1] = a[i];

   571                 }

   572                 a[i + 1] = ai;

   573             }

   574         }

   575     }

   576 

   577     /**

   578      * Sorts the specified range of the array using heap sort.

   579      *

   580      * @param a the array to be sorted

   581      * @param low the index of the first element, inclusive, to be sorted

   582      * @param high the index of the last element, exclusive, to be sorted

   583      */

   584     private static void heapSort(int[] a, int low, int high) {

   585         for (int k = (low + high) >>> 1; k > low; ) {

   586             pushDown(a, --k, a[k], low, high);

   587         }

   588         while (--high > low) {

   589             int max = a[low];

   590             pushDown(a, low, a[high], low, high);

   591             a[high] = max;

   592         }

   593     }

   594 

   595     /**

   596      * Pushes specified element down during heap sort.

   597      *

   598      * @param a the given array

   599      * @param p the start index

   600      * @param value the given element

   601      * @param low the index of the first element, inclusive, to be sorted

   602      * @param high the index of the last element, exclusive, to be sorted

   603      */

   604     private static void pushDown(int[] a, int p, int value, int low, int high) {

   605         for (int k ;; a[p] = a[p = k]) {

   606             k = (p << 1) - low + 2; // Index of the right child

   607 

   608             if (k > high) {

   609                 break;

   610             }

   611             if (k == high || a[k] < a[k - 1]) {

   612                 --k;

   613             }

   614             if (a[k] <= value) {

   615                 break;

   616             }

   617         }

   618         a[p] = value;

   619     }

   620 

   621     /**

   622      * Tries to sort the specified range of the array.

   623      *

   624      * @param sorter parallel context

   625      * @param a the array to be sorted

   626      * @param low the index of the first element to be sorted

   627      * @param size the array size

   628      * @return true if finally sorted, false otherwise

   629      */

   630     private static boolean tryMergeRuns(Sorter sorter, int[] a, int low, int size) {

   631 

   632         /*

   633          * The run array is constructed only if initial runs are

   634          * long enough to continue, run[i] then holds start index

   635          * of the i-th sequence of elements in non-descending order.

   636          */

   637         int[] run = null;

   638         int high = low + size;

   639         int count = 1, last = low;

   640 

   641         /*

   642          * Identify all possible runs.

   643          */

   644         for (int k = low + 1; k < high; ) {

   645 

   646             /*

   647              * Find the end index of the current run.

   648              */

   649             if (a[k - 1] < a[k]) {

   650 

   651                 // Identify ascending sequence

   652                 while (++k < high && a[k - 1] <= a[k]);

   653 

   654             } else if (a[k - 1] > a[k]) {

   655 

   656                 // Identify descending sequence

   657                 while (++k < high && a[k - 1] >= a[k]);

   658 

   659                 // Reverse into ascending order

   660                 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {

   661                     int ai = a[i]; a[i] = a[j]; a[j] = ai;

   662                 }

   663             } else { // Identify constant sequence

   664                 for (int ak = a[k]; ++k < high && ak == a[k]; );

   665 

   666                 if (k < high) {

   667                     continue;

   668                 }

   669             }

   670 

   671             /*

   672              * Check special cases.

   673              */

   674             if (run == null) {

   675                 if (k == high) {

   676 

   677                     /*

   678                      * The array is monotonous sequence,

   679                      * and therefore already sorted.

   680                      */

   681                     return true;

   682                 }

   683 

   684                 if (k - low < MIN_FIRST_RUN_SIZE) {

   685 

   686                     /*

   687                      * The first run is too small

   688                      * to proceed with scanning.

   689                      */

   690                     return false;

   691                 }

   692 

   693                 run = new int[((size >> 10) | 0x7F) & 0x3FF];

   694                 run[0] = low;

   695 

   696             } else if (a[last - 1] > a[last]) {

   697 

   698                 if (count > (k - low) >> MIN_FIRST_RUNS_FACTOR) {

   699 

   700                     /*

   701                      * The first runs are not long

   702                      * enough to continue scanning.

   703                      */

   704                     return false;

   705                 }

   706 

   707                 if (++count == MAX_RUN_CAPACITY) {

   708 

   709                     /*

   710                      * Array is not highly structured.

   711                      */

   712                     return false;

   713                 }

   714 

   715                 if (count == run.length) {

   716 

   717                     /*

   718                      * Increase capacity of index array.

   719                      */

   720                     run = Arrays.copyOf(run, count << 1);

   721                 }

   722             }

   723             run[count] = (last = k);

   724         }

   725 

   726         /*

   727          * Merge runs of highly structured array.

   728          */

   729         if (count > 1) {

   730             int[] b; int offset = low;

   731 

   732             if (sorter == null || (b = (int[]) sorter.b) == null) {

   733                 b = new int[size];

   734             } else {

   735                 offset = sorter.offset;

   736             }

   737             mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);

   738         }

   739         return true;

   740     }

   741 

   742     /**

   743      * Merges the specified runs.

   744      *

   745      * @param a the source array

   746      * @param b the temporary buffer used in merging

   747      * @param offset the start index in the source, inclusive

   748      * @param aim specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)

   749      * @param parallel indicates whether merging is performed in parallel

   750      * @param run the start indexes of the runs, inclusive

   751      * @param lo the start index of the first run, inclusive

   752      * @param hi the start index of the last run, inclusive

   753      * @return the destination where runs are merged

   754      */

   755     private static int[] mergeRuns(int[] a, int[] b, int offset,

   756             int aim, boolean parallel, int[] run, int lo, int hi) {

   757 

   758         if (hi - lo == 1) {

   759             if (aim >= 0) {

   760                 return a;

   761             }

   762             for (int i = run[hi], j = i - offset, low = run[lo]; i > low;

   763                 b[--j] = a[--i]

   764             );

   765             return b;

   766         }

   767 

   768         /*

   769          * Split into approximately equal parts.

   770          */

   771         int mi = lo, rmi = (run[lo] + run[hi]) >>> 1;

   772         while (run[++mi + 1] <= rmi);

   773 

   774         /*

   775          * Merge the left and right parts.

   776          */

   777         int[] a1, a2;

   778 

   779         if (parallel && hi - lo > MIN_RUN_COUNT) {

   780             RunMerger merger = new RunMerger(a, b, offset, 0, run, mi, hi).forkMe();

   781             a1 = mergeRuns(a, b, offset, -aim, true, run, lo, mi);

   782             a2 = (int[]) merger.getDestination();

   783         } else {

   784             a1 = mergeRuns(a, b, offset, -aim, false, run, lo, mi);

   785             a2 = mergeRuns(a, b, offset,    0, false, run, mi, hi);

   786         }

   787 

   788         int[] dst = a1 == a ? b : a;

   789 

   790         int k   = a1 == a ? run[lo] - offset : run[lo];

   791         int lo1 = a1 == b ? run[lo] - offset : run[lo];

   792         int hi1 = a1 == b ? run[mi] - offset : run[mi];

   793         int lo2 = a2 == b ? run[mi] - offset : run[mi];

   794         int hi2 = a2 == b ? run[hi] - offset : run[hi];

   795 

   796         if (parallel) {

   797             new Merger(null, dst, k, a1, lo1, hi1, a2, lo2, hi2).invoke();

   798         } else {

   799             mergeParts(null, dst, k, a1, lo1, hi1, a2, lo2, hi2);

   800         }

   801         return dst;

   802     }

   803 

   804     /**

   805      * Merges the sorted parts.

   806      *

   807      * @param merger parallel context

   808      * @param dst the destination where parts are merged

   809      * @param k the start index of the destination, inclusive

   810      * @param a1 the first part

   811      * @param lo1 the start index of the first part, inclusive

   812      * @param hi1 the end index of the first part, exclusive

   813      * @param a2 the second part

   814      * @param lo2 the start index of the second part, inclusive

   815      * @param hi2 the end index of the second part, exclusive

   816      */

   817     private static void mergeParts(Merger merger, int[] dst, int k,

   818             int[] a1, int lo1, int hi1, int[] a2, int lo2, int hi2) {

   819 

   820         if (merger != null && a1 == a2) {

   821 

   822             while (true) {

   823 

   824                 /*

   825                  * The first part must be larger.

   826                  */

   827                 if (hi1 - lo1 < hi2 - lo2) {

   828                     int lo = lo1; lo1 = lo2; lo2 = lo;

   829                     int hi = hi1; hi1 = hi2; hi2 = hi;

   830                 }

   831 

   832                 /*

   833                  * Small parts will be merged sequentially.

   834                  */

   835                 if (hi1 - lo1 < MIN_PARALLEL_MERGE_PARTS_SIZE) {

   836                     break;

   837                 }

   838 

   839                 /*

   840                  * Find the median of the larger part.

   841                  */

   842                 int mi1 = (lo1 + hi1) >>> 1;

   843                 int key = a1[mi1];

   844                 int mi2 = hi2;

   845 

   846                 /*

   847                  * Partition the smaller part.

   848                  */

   849                 for (int loo = lo2; loo < mi2; ) {

   850                     int t = (loo + mi2) >>> 1;

   851 

   852                     if (key > a2[t]) {

   853                         loo = t + 1;

   854                     } else {

   855                         mi2 = t;

   856                     }

   857                 }

   858 

   859                 int d = mi2 - lo2 + mi1 - lo1;

   860 

   861                 /*

   862                  * Merge the right sub-parts in parallel.

   863                  */

   864                 merger.forkMerger(dst, k + d, a1, mi1, hi1, a2, mi2, hi2);

   865 

   866                 /*

   867                  * Process the sub-left parts.

   868                  */

   869                 hi1 = mi1;

   870                 hi2 = mi2;

   871             }

   872         }

   873 

   874         /*

   875          * Merge small parts sequentially.

   876          */

   877         while (lo1 < hi1 && lo2 < hi2) {

   878             dst[k++] = a1[lo1] < a2[lo2] ? a1[lo1++] : a2[lo2++];

   879         }

   880         if (dst != a1 || k < lo1) {

   881             while (lo1 < hi1) {

   882                 dst[k++] = a1[lo1++];

   883             }

   884         }

   885         if (dst != a2 || k < lo2) {

   886             while (lo2 < hi2) {

   887                 dst[k++] = a2[lo2++];

   888             }

   889         }

   890     }

   891 

   892 // [long]

   893 

   894     /**

   895      * Sorts the specified range of the array using parallel merge

   896      * sort and/or Dual-Pivot Quicksort.

   897      *

   898      * To balance the faster splitting and parallelism of merge sort

   899      * with the faster element partitioning of Quicksort, ranges are

   900      * subdivided in tiers such that, if there is enough parallelism,

   901      * the four-way parallel merge is started, still ensuring enough

   902      * parallelism to process the partitions.

   903      *

   904      * @param a the array to be sorted

   905      * @param parallelism the parallelism level

   906      * @param low the index of the first element, inclusive, to be sorted

   907      * @param high the index of the last element, exclusive, to be sorted

   908      */

   909     static void sort(long[] a, int parallelism, int low, int high) {

   910         int size = high - low;

   911 

   912         if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {

   913             int depth = getDepth(parallelism, size >> 12);

   914             long[] b = depth == 0 ? null : new long[size];

   915             new Sorter(null, a, b, low, size, low, depth).invoke();

   916         } else {

   917             sort(null, a, 0, low, high);

   918         }

   919     }

   920 

   921     /**

   922      * Sorts the specified array using the Dual-Pivot Quicksort and/or

   923      * other sorts in special-cases, possibly with parallel partitions.

   924      *

   925      * @param sorter parallel context

   926      * @param a the array to be sorted

   927      * @param bits the combination of recursion depth and bit flag, where

   928      *        the right bit "0" indicates that array is the leftmost part

   929      * @param low the index of the first element, inclusive, to be sorted

   930      * @param high the index of the last element, exclusive, to be sorted

   931      */

   932     static void sort(Sorter sorter, long[] a, int bits, int low, int high) {

   933         while (true) {

   934             int end = high - 1, size = high - low;

   935 

   936             /*

   937              * Run mixed insertion sort on small non-leftmost parts.

   938              */

   939             if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {

   940                 mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);

   941                 return;

   942             }

   943 

   944             /*

   945              * Invoke insertion sort on small leftmost part.

   946              */

   947             if (size < MAX_INSERTION_SORT_SIZE) {

   948                 insertionSort(a, low, high);

   949                 return;

   950             }

   951 

   952             /*

   953              * Check if the whole array or large non-leftmost

   954              * parts are nearly sorted and then merge runs.

   955              */

   956             if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)

   957                     && tryMergeRuns(sorter, a, low, size)) {

   958                 return;

   959             }

   960 

   961             /*

   962              * Switch to heap sort if execution