1 /*
   2  * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation. Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.util.concurrent.ForkJoinTask;
  29 import java.util.concurrent.RecursiveAction;
  30 
  31 /**
  32  * This class implements powerful and fully optimized versions, both
  33  * sequential and parallel, of the Dual-Pivot Quicksort algorithm by
  34  * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
  35  * offers O(n log(n)) performance on all data sets, and is typically
  36  * faster than traditional (one-pivot) Quicksort implementations.
  37  *
  38  * @author Vladimir Yaroslavskiy
  39  * @author Jon Bentley
  40  * @author Josh Bloch
  41  *
  42  * @version 2018.02.18
  43  * @since 1.7
  44  */
  45 final class DualPivotQuicksort {
  46 
  47     /**
  48      * Prevents instantiation.
  49      */
  50     private DualPivotQuicksort() {}
  51 
  52     /**
  53      * If the length of the leftmost part to be sorted is less than
  54      * this constant, heap sort is used in preference to Quicksort.
  55      */
  56     private static final int HEAP_SORT_THRESHOLD = 69;
  57 
  58     /**
  59      * If the length of non-leftmost part to be sorted is less than this
  60      * constant, nano insertion sort is used in preference to Quicksort.
  61      */
  62     private static final int NANO_INSERTION_SORT_THRESHOLD = 36;
  63 
  64     /**
  65      * If the length of non-leftmost part to be sorted is less than this
  66      * constant, pair insertion sort is used in preference to Quicksort.
  67      */
  68     private static final int PAIR_INSERTION_SORT_THRESHOLD = 88;
  69 
  70     /**
  71      * The minimal length of an array, required by parallel Quicksort.
  72      */
  73     private static final int PARALLEL_QUICKSORT_THRESHOLD = 1024;
  74 
  75     /**
  76      * If the length of a byte array to be sorted is greater than this
  77      * constant, counting sort is used in preference to insertion sort.
  78      */
  79     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 41;
  80 
  81     /**
  82      * If the length of a short or char array to be sorted is greater
  83      * than this constant, counting sort is used in preference to Quicksort.
  84      */
  85     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 2180;
  86 
  87     /**
  88      * if the depth of the Quicksort recursion exceeds this
  89      * constant, heap sort is used in preference to Quicksort.
  90      */
  91     private static final int MAX_RECURSION_DEPTH = 100;
  92 
  93     /**
  94      * This constant is combination of maximum Quicksort recursion depth
  95      * and binary flag, where the right bit "0" indicates that the whole
  96      * array is considered as the leftmost part.
  97      */
  98     private static final int LEFTMOST_BITS = MAX_RECURSION_DEPTH << 1;
  99 
 100     /**
 101      * This class implements the parallel Dual-Pivot Quicksort.
 102      */
 103     @SuppressWarnings("serial")
 104     private static class Sorter<T> extends RecursiveAction {
 105 
 106         Sorter(T a, int bits, int low, int high) {
 107             this.a = a;
 108             this.bits = bits;
 109             this.low = low;
 110             this.high = high;
 111         }
 112 
 113         @Override
 114         protected void compute() {
 115             Class<?> clazz = a.getClass();
 116 
 117             if (clazz == int[].class) {
 118                 sort((int[]) a, bits, true, low, high);
 119             } else if (clazz == long[].class) {
 120                 sort((long[]) a, bits, true, low, high);
 121             } else if (clazz == char[].class) {
 122                 sort((char[]) a, bits, true, low, high);
 123             } else if (clazz == short[].class) {
 124                 sort((short[]) a, bits, true, low, high);
 125             } else if (clazz == float[].class) {
 126                 sort((float[]) a, bits, true, low, high);
 127             } else if (clazz == double[].class) {
 128                 sort((double[]) a, bits, true, low, high);
 129             } else {
 130                 throw new IllegalArgumentException(
 131                     "Unknown type of array: " + clazz.getName());
 132             }
 133         }
 134 
 135         private T a;
 136         private int bits;
 137         private int low;
 138         private int high;
 139     }
 140 
 141     /**
 142      * Sorts the specified range of the array.
 143      *
 144      * @param a the array to be sorted
 145      * @param parallel indicates whether sorting is performed in parallel
 146      * @param low the index of the first element, inclusive, to be sorted
 147      * @param high the index of the last element, exclusive, to be sorted
 148      */
 149     static void sort(int[] a, boolean parallel, int low, int high) {
 150         sort(a, LEFTMOST_BITS, parallel, low, high);
 151     }
 152 
 153     /**
 154      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
 155      *
 156      * @param a the array to be sorted
 157      * @param bits the recursion depth of Quicksort and the leftmost flag
 158      * @param parallel indicates whether sorting is performed in parallel
 159      * @param low the index of the first element, inclusive, to be sorted
 160      * @param high the index of the last element, exclusive, to be sorted
 161      */
 162     private static void sort(int[] a, int bits, boolean parallel, int low, int high) {
 163         int end = high - 1, length = high - low;
 164 
 165         /*
 166          * Run insertion sorts on non-leftmost part.
 167          */
 168         if ((bits & 1) > 0) {
 169 
 170             /*
 171              * Use nano insertion sort on tiny part.
 172              */
 173             if (length < NANO_INSERTION_SORT_THRESHOLD) {
 174                 SortingAlgorithms.nanoInsertionSort(a, low, high);
 175                 return;
 176             }
 177 
 178             /*
 179              * Use pair insertion sort on small part.
 180              */
 181             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
 182                 SortingAlgorithms.pairInsertionSort(a, low, end);
 183                 return;
 184             }
 185         }
 186 
 187         /*
 188          * Switch to heap sort on the leftmost part or
 189          * if the execution time is becoming quadratic.
 190          */
 191         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
 192             SortingAlgorithms.heapSort(a, low, end);
 193             return;
 194         }
 195 
 196         /*
 197          * Check if the array is nearly sorted
 198          * and then try to sort it by Merging sort.
 199          */
 200         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
 201             return;
 202         }
 203 
 204         /*
 205          * The splitting of the array, defined by the following
 206          * step, is related to the inexpensive approximation of
 207          * the golden ratio.
 208          */
 209         int step = (length >> 3) * 3 + 3;
 210 
 211         /*
 212          * Five elements around (and including) the central element in
 213          * the array will be used for pivot selection as described below.
 214          * The unequal choice of spacing these elements was empirically
 215          * determined to work well on a wide variety of inputs.
 216          */
 217         int e1 = low + step;
 218         int e5 = end - step;
 219         int e3 = (e1 + e5) >>> 1;
 220         int e2 = (e1 + e3) >>> 1;
 221         int e4 = (e3 + e5) >>> 1;
 222 
 223         /*
 224          * Sort these elements in place by the combination
 225          * of 5-element sorting network and insertion sort.
 226          */
 227         if (a[e5] < a[e3]) { int t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
 228         if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
 229         if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
 230         if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
 231         if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
 232 
 233         if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t;
 234             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
 235                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
 236                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
 237                 }
 238             }
 239         }
 240 
 241         // Pointers
 242         int lower = low; // The index of the last element of the left part
 243         int upper = end; // The index of the first element of the right part
 244 
 245         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
 246 
 247             /*
 248              * Use the first and the fifth elements as the pivots.
 249              * These values are inexpensive approximation of tertiles.
 250              * Note, that pivot1 < pivot2.
 251              */
 252             int pivot1 = a[e1];
 253             int pivot2 = a[e5];
 254 
 255             /*
 256              * The first and the last elements to be sorted are moved to the
 257              * locations formerly occupied by the pivots. When partitioning
 258              * is completed, the pivots are swapped back into their final
 259              * positions, and excluded from subsequent sorting.
 260              */
 261             a[e1] = a[lower];
 262             a[e5] = a[upper];
 263 
 264             /*
 265              * Skip elements, which are less or greater than the pivots.
 266              */
 267             while (a[++lower] < pivot1);
 268             while (a[--upper] > pivot2);
 269 
 270             /*
 271              * Backwards 3-interval partitioning
 272              *
 273              *   left part                 central part          right part
 274              * +------------------------------------------------------------+
 275              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
 276              * +------------------------------------------------------------+
 277              *             ^       ^                            ^
 278              *             |       |                            |
 279              *           lower     k                          upper
 280              *
 281              * Invariants:
 282              *
 283              *              all in (low, lower] < pivot1
 284              *    pivot1 <= all in (k, upper)  <= pivot2
 285              *              all in [upper, end) > pivot2
 286              *
 287              * Pointer k is the last index of ?-part
 288              */
 289             for (int $ = --lower, k = ++upper; --k > lower; ) {
 290                 int ak = a[k];
 291 
 292                 if (ak < pivot1) { // Move a[k] to the left side
 293                     while (a[++lower] < pivot1);
 294 
 295                     if (lower > k) {
 296                         lower = k;
 297                         break;
 298                     }
 299                     if (a[lower] > pivot2) { // a[lower] >= pivot1
 300                         a[k] = a[--upper];
 301                         a[upper] = a[lower];
 302                     } else { // pivot1 <= a[lower] <= pivot2
 303                         a[k] = a[lower];
 304                     }
 305                     a[lower] = ak;
 306                 } else if (ak > pivot2) { // Move a[k] to the right side
 307                     a[k] = a[--upper];
 308                     a[upper] = ak;
 309                 }
 310             }
 311 
 312             /*
 313              * Swap the pivots into their final positions.
 314              */
 315             a[low] = a[lower]; a[lower] = pivot1;
 316             a[end] = a[upper]; a[upper] = pivot2;
 317 
 318             /*
 319              * Sort all parts recursively, excluding known pivots.
 320              */
 321             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 322                 ForkJoinTask.invokeAll(
 323                     new Sorter<int[]>(a, bits | 1, lower + 1, upper),
 324                     new Sorter<int[]>(a, bits | 1, upper + 1, high),
 325                     new Sorter<int[]>(a, bits, low, lower)
 326                 );
 327             } else {
 328                 sort(a, bits | 1, false, upper + 1, high);
 329                 sort(a, bits, false, low, lower);
 330                 sort(a, bits | 1, false, lower + 1, upper);
 331             }
 332         } else { // Partitioning with one pivot
 333 
 334             /*
 335              * Use the third element as the pivot. This value
 336              * is inexpensive approximation of the median.
 337              */
 338             int pivot = a[e3];
 339 
 340             /*
 341              * The first element to be sorted is moved to the location
 342              * formerly occupied by the pivot. When partitioning is
 343              * completed, the pivot is swapped back into its final
 344              * position, and excluded from subsequent sorting.
 345              */
 346             a[e3] = a[lower];
 347 
 348             /*
 349              * Traditional 3-way (Dutch National Flag) partitioning
 350              *
 351              *   left part                 central part    right part
 352              * +------------------------------------------------------+
 353              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
 354              * +------------------------------------------------------+
 355              *              ^           ^                ^
 356              *              |           |                |
 357              *            lower         k              upper
 358              *
 359              * Invariants:
 360              *
 361              *   all in (low, lower] < pivot
 362              *   all in (k, upper)  == pivot
 363              *   all in [upper, end] > pivot
 364              *
 365              * Pointer k is the last index of ?-part
 366              */
 367             for (int k = ++upper; --k > lower; ) {
 368                 if (a[k] == pivot) {
 369                     continue;
 370                 }
 371                 int ak = a[k];
 372 
 373                 if (ak < pivot) { // Move a[k] to the left side
 374                     while (a[++lower] < pivot);
 375 
 376                     if (lower > k) {
 377                         lower = k;
 378                         break;
 379                     }
 380                     a[k] = pivot;
 381 
 382                     if (a[lower] > pivot) {
 383                         a[--upper] = a[lower];
 384                     }
 385                     a[lower] = ak;
 386                 } else { // ak > pivot - Move a[k] to the right side
 387                     a[k] = pivot;
 388                     a[--upper] = ak;
 389                 }
 390             }
 391 
 392             /*
 393              * Swap the pivot into its final position.
 394              */
 395             a[low] = a[lower]; a[lower] = pivot;
 396 
 397             /*
 398              * Sort the left and the right parts recursively, excluding
 399              * known pivot. All elements from the central part are equal
 400              * and, therefore, already sorted.
 401              */
 402             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 403                 ForkJoinTask.invokeAll(
 404                     new Sorter<int[]>(a, bits, low, lower),
 405                     new Sorter<int[]>(a, bits | 1, upper, high)
 406                 );
 407             } else {
 408                 sort(a, bits | 1, false, upper, high);
 409                 sort(a, bits, false, low, lower);
 410             }
 411         }
 412     }
 413 
 414     /**
 415      * Sorts the specified range of the array.
 416      *
 417      * @param a the array to be sorted
 418      * @param parallel indicates whether sorting is performed in parallel
 419      * @param low the index of the first element, inclusive, to be sorted
 420      * @param high the index of the last element, exclusive, to be sorted
 421      */
 422     static void sort(long[] a, boolean parallel, int low, int high) {
 423         sort(a, LEFTMOST_BITS, parallel, low, high);
 424     }
 425 
 426     /**
 427      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
 428      *
 429      * @param a the array to be sorted
 430      * @param bits the recursion depth of Quicksort and the leftmost flag
 431      * @param parallel indicates whether sorting is performed in parallel
 432      * @param low the index of the first element, inclusive, to be sorted
 433      * @param high the index of the last element, exclusive, to be sorted
 434      */
 435     private static void sort(long[] a, int bits, boolean parallel, int low, int high) {
 436         int end = high - 1, length = high - low;
 437 
 438         /*
 439          * Run insertion sorts on non-leftmost part.
 440          */
 441         if ((bits & 1) > 0) {
 442 
 443             /*
 444              * Use nano insertion sort on tiny part.
 445              */
 446             if (length < NANO_INSERTION_SORT_THRESHOLD) {
 447                 SortingAlgorithms.nanoInsertionSort(a, low, high);
 448                 return;
 449             }
 450 
 451             /*
 452              * Use pair insertion sort on small part.
 453              */
 454             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
 455                 SortingAlgorithms.pairInsertionSort(a, low, end);
 456                 return;
 457             }
 458         }
 459 
 460         /*
 461          * Switch to heap sort on the leftmost part or
 462          * if the execution time is becoming quadratic.
 463          */
 464         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
 465             SortingAlgorithms.heapSort(a, low, end);
 466             return;
 467         }
 468 
 469         /*
 470          * Check if the array is nearly sorted
 471          * and then try to sort it by Merging sort.
 472          */
 473         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
 474             return;
 475         }
 476 
 477         /*
 478          * The splitting of the array, defined by the following
 479          * step, is related to the inexpensive approximation of
 480          * the golden ratio.
 481          */
 482         int step = (length >> 3) * 3 + 3;
 483 
 484         /*
 485          * Five elements around (and including) the central element in
 486          * the array will be used for pivot selection as described below.
 487          * The unequal choice of spacing these elements was empirically
 488          * determined to work well on a wide variety of inputs.
 489          */
 490         int e1 = low + step;
 491         int e5 = end - step;
 492         int e3 = (e1 + e5) >>> 1;
 493         int e2 = (e1 + e3) >>> 1;
 494         int e4 = (e3 + e5) >>> 1;
 495 
 496         /*
 497          * Sort these elements in place by the combination
 498          * of 5-element sorting network and insertion sort.
 499          */
 500         if (a[e5] < a[e3]) { long t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
 501         if (a[e4] < a[e2]) { long t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
 502         if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
 503         if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
 504         if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
 505 
 506         if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t;
 507             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
 508                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
 509                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
 510                 }
 511             }
 512         }
 513 
 514         // Pointers
 515         int lower = low; // The index of the last element of the left part
 516         int upper = end; // The index of the first element of the right part
 517 
 518         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
 519 
 520             /*
 521              * Use the first and the fifth elements as the pivots.
 522              * These values are inexpensive approximation of tertiles.
 523              * Note, that pivot1 < pivot2.
 524              */
 525             long pivot1 = a[e1];
 526             long pivot2 = a[e5];
 527 
 528             /*
 529              * The first and the last elements to be sorted are moved to the
 530              * locations formerly occupied by the pivots. When partitioning
 531              * is completed, the pivots are swapped back into their final
 532              * positions, and excluded from subsequent sorting.
 533              */
 534             a[e1] = a[lower];
 535             a[e5] = a[upper];
 536 
 537             /*
 538              * Skip elements, which are less or greater than the pivots.
 539              */
 540             while (a[++lower] < pivot1);
 541             while (a[--upper] > pivot2);
 542 
 543             /*
 544              * Backwards 3-interval partitioning
 545              *
 546              *   left part                 central part          right part
 547              * +------------------------------------------------------------+
 548              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
 549              * +------------------------------------------------------------+
 550              *             ^       ^                            ^
 551              *             |       |                            |
 552              *           lower     k                          upper
 553              *
 554              * Invariants:
 555              *
 556              *              all in (low, lower] < pivot1
 557              *    pivot1 <= all in (k, upper)  <= pivot2
 558              *              all in [upper, end) > pivot2
 559              *
 560              * Pointer k is the last index of ?-part
 561              */
 562             for (int $ = --lower, k = ++upper; --k > lower; ) {
 563                 long ak = a[k];
 564 
 565                 if (ak < pivot1) { // Move a[k] to the left side
 566                     while (a[++lower] < pivot1);
 567 
 568                     if (lower > k) {
 569                         lower = k;
 570                         break;
 571                     }
 572                     if (a[lower] > pivot2) { // a[lower] >= pivot1
 573                         a[k] = a[--upper];
 574                         a[upper] = a[lower];
 575                     } else { // pivot1 <= a[lower] <= pivot2
 576                         a[k] = a[lower];
 577                     }
 578                     a[lower] = ak;
 579                 } else if (ak > pivot2) { // Move a[k] to the right side
 580                     a[k] = a[--upper];
 581                     a[upper] = ak;
 582                 }
 583             }
 584 
 585             /*
 586              * Swap the pivots into their final positions.
 587              */
 588             a[low] = a[lower]; a[lower] = pivot1;
 589             a[end] = a[upper]; a[upper] = pivot2;
 590 
 591             /*
 592              * Sort all parts recursively, excluding known pivots.
 593              */
 594             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 595                 ForkJoinTask.invokeAll(
 596                     new Sorter<long[]>(a, bits | 1, lower + 1, upper),
 597                     new Sorter<long[]>(a, bits | 1, upper + 1, high),
 598                     new Sorter<long[]>(a, bits, low, lower)
 599                 );
 600             } else {
 601                 sort(a, bits | 1, false, upper + 1, high);
 602                 sort(a, bits, false, low, lower);
 603                 sort(a, bits | 1, false, lower + 1, upper);
 604             }
 605         } else { // Partitioning with one pivot
 606 
 607             /*
 608              * Use the third element as the pivot. This value
 609              * is inexpensive approximation of the median.
 610              */
 611             long pivot = a[e3];
 612 
 613             /*
 614              * The first element to be sorted is moved to the location
 615              * formerly occupied by the pivot. When partitioning is
 616              * completed, the pivot is swapped back into its final
 617              * position, and excluded from subsequent sorting.
 618              */
 619             a[e3] = a[lower];
 620 
 621             /*
 622              * Traditional 3-way (Dutch National Flag) partitioning
 623              *
 624              *   left part                 central part    right part
 625              * +------------------------------------------------------+
 626              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
 627              * +------------------------------------------------------+
 628              *              ^           ^                ^
 629              *              |           |                |
 630              *            lower         k              upper
 631              *
 632              * Invariants:
 633              *
 634              *   all in (low, lower] < pivot
 635              *   all in (k, upper)  == pivot
 636              *   all in [upper, end] > pivot
 637              *
 638              * Pointer k is the last index of ?-part
 639              */
 640             for (int k = ++upper; --k > lower; ) {
 641                 if (a[k] == pivot) {
 642                     continue;
 643                 }
 644                 long ak = a[k];
 645 
 646                 if (ak < pivot) { // Move a[k] to the left side
 647                     while (a[++lower] < pivot);
 648 
 649                     if (lower > k) {
 650                         lower = k;
 651                         break;
 652                     }
 653                     a[k] = pivot;
 654 
 655                     if (a[lower] > pivot) {
 656                         a[--upper] = a[lower];
 657                     }
 658                     a[lower] = ak;
 659                 } else { // ak > pivot - Move a[k] to the right side
 660                     a[k] = pivot;
 661                     a[--upper] = ak;
 662                 }
 663             }
 664 
 665             /*
 666              * Swap the pivot into its final position.
 667              */
 668             a[low] = a[lower]; a[lower] = pivot;
 669 
 670             /*
 671              * Sort the left and the right parts recursively, excluding
 672              * known pivot. All elements from the central part are equal
 673              * and, therefore, already sorted.
 674              */
 675             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 676                 ForkJoinTask.invokeAll(
 677                     new Sorter<long[]>(a, bits, low, lower),
 678                     new Sorter<long[]>(a, bits | 1, upper, high)
 679                 );
 680             } else {
 681                 sort(a, bits | 1, false, upper, high);
 682                 sort(a, bits, false, low, lower);
 683             }
 684         }
 685     }
 686 
 687     /**
 688      * Sorts the specified range of the array.
 689      *
 690      * @param a the array to be sorted
 691      * @param parallel indicates whether sorting is performed in parallel
 692      * @param low the index of the first element, inclusive, to be sorted
 693      * @param high the index of the last element, exclusive, to be sorted
 694      */
 695     static void sort(byte[] a, boolean parallel, int low, int high) {
 696         if (high - low > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
 697             SortingAlgorithms.countingSort(a, low, high);
 698         } else {
 699             SortingAlgorithms.insertionSort(a, low, high);
 700         }
 701     }
 702 
 703     /**
 704      * Sorts the specified range of the array.
 705      *
 706      * @param a the array to be sorted
 707      * @param parallel indicates whether sorting is performed in parallel
 708      * @param low the index of the first element, inclusive, to be sorted
 709      * @param high the index of the last element, exclusive, to be sorted
 710      */
 711     static void sort(char[] a, boolean parallel, int low, int high) {
 712         if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
 713             SortingAlgorithms.countingSort(a, low, high);
 714         } else {
 715             sort(a, LEFTMOST_BITS, parallel, low, high);
 716         }
 717     }
 718 
 719     /**
 720      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
 721      *
 722      * @param a the array to be sorted
 723      * @param bits the recursion depth of Quicksort and the leftmost flag
 724      * @param parallel indicates whether sorting is performed in parallel
 725      * @param low the index of the first element, inclusive, to be sorted
 726      * @param high the index of the last element, exclusive, to be sorted
 727      */
 728     private static void sort(char[] a, int bits, boolean parallel, int low, int high) {
 729         int end = high - 1, length = high - low;
 730 
 731         /*
 732          * Run insertion sorts on non-leftmost part.
 733          */
 734         if ((bits & 1) > 0) {
 735 
 736             /*
 737              * Use nano insertion sort on tiny part.
 738              */
 739             if (length < NANO_INSERTION_SORT_THRESHOLD) {
 740                 SortingAlgorithms.nanoInsertionSort(a, low, high);
 741                 return;
 742             }
 743 
 744             /*
 745              * Use pair insertion sort on small part.
 746              */
 747             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
 748                 SortingAlgorithms.pairInsertionSort(a, low, end);
 749                 return;
 750             }
 751         }
 752 
 753         /*
 754          * Switch to heap sort on the leftmost part or
 755          * if the execution time is becoming quadratic.
 756          */
 757         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
 758             SortingAlgorithms.heapSort(a, low, end);
 759             return;
 760         }
 761 
 762         /*
 763          * Check if the array is nearly sorted
 764          * and then try to sort it by Merging sort.
 765          */
 766         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
 767             return;
 768         }
 769 
 770         /*
 771          * The splitting of the array, defined by the following
 772          * step, is related to the inexpensive approximation of
 773          * the golden ratio.
 774          */
 775         int step = (length >> 3) * 3 + 3;
 776 
 777         /*
 778          * Five elements around (and including) the central element in
 779          * the array will be used for pivot selection as described below.
 780          * The unequal choice of spacing these elements was empirically
 781          * determined to work well on a wide variety of inputs.
 782          */
 783         int e1 = low + step;
 784         int e5 = end - step;
 785         int e3 = (e1 + e5) >>> 1;
 786         int e2 = (e1 + e3) >>> 1;
 787         int e4 = (e3 + e5) >>> 1;
 788 
 789         /*
 790          * Sort these elements in place by the combination
 791          * of 5-element sorting network and insertion sort.
 792          */
 793         if (a[e5] < a[e3]) { char t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
 794         if (a[e4] < a[e2]) { char t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
 795         if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
 796         if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
 797         if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
 798 
 799         if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t;
 800             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
 801                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
 802                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
 803                 }
 804             }
 805         }
 806 
 807         // Pointers
 808         int lower = low; // The index of the last element of the left part
 809         int upper = end; // The index of the first element of the right part
 810 
 811         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
 812 
 813             /*
 814              * Use the first and the fifth elements as the pivots.
 815              * These values are inexpensive approximation of tertiles.
 816              * Note, that pivot1 < pivot2.
 817              */
 818             char pivot1 = a[e1];
 819             char pivot2 = a[e5];
 820 
 821             /*
 822              * The first and the last elements to be sorted are moved to the
 823              * locations formerly occupied by the pivots. When partitioning
 824              * is completed, the pivots are swapped back into their final
 825              * positions, and excluded from subsequent sorting.
 826              */
 827             a[e1] = a[lower];
 828             a[e5] = a[upper];
 829 
 830             /*
 831              * Skip elements, which are less or greater than the pivots.
 832              */
 833             while (a[++lower] < pivot1);
 834             while (a[--upper] > pivot2);
 835 
 836             /*
 837              * Backwards 3-interval partitioning
 838              *
 839              *   left part                 central part          right part
 840              * +------------------------------------------------------------+
 841              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
 842              * +------------------------------------------------------------+
 843              *             ^       ^                            ^
 844              *             |       |                            |
 845              *           lower     k                          upper
 846              *
 847              * Invariants:
 848              *
 849              *              all in (low, lower] < pivot1
 850              *    pivot1 <= all in (k, upper)  <= pivot2
 851              *              all in [upper, end) > pivot2
 852              *
 853              * Pointer k is the last index of ?-part
 854              */
 855             for (int $ = --lower, k = ++upper; --k > lower; ) {
 856                 char ak = a[k];
 857 
 858                 if (ak < pivot1) { // Move a[k] to the left side
 859                     while (a[++lower] < pivot1);
 860 
 861                     if (lower > k) {
 862                         lower = k;
 863                         break;
 864                     }
 865                     if (a[lower] > pivot2) { // a[lower] >= pivot1
 866                         a[k] = a[--upper];
 867                         a[upper] = a[lower];
 868                     } else { // pivot1 <= a[lower] <= pivot2
 869                         a[k] = a[lower];
 870                     }
 871                     a[lower] = ak;
 872                 } else if (ak > pivot2) { // Move a[k] to the right side
 873                     a[k] = a[--upper];
 874                     a[upper] = ak;
 875                 }
 876             }
 877 
 878             /*
 879              * Swap the pivots into their final positions.
 880              */
 881             a[low] = a[lower]; a[lower] = pivot1;
 882             a[end] = a[upper]; a[upper] = pivot2;
 883 
 884             /*
 885              * Sort all parts recursively, excluding known pivots.
 886              */
 887             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 888                 ForkJoinTask.invokeAll(
 889                     new Sorter<char[]>(a, bits | 1, lower + 1, upper),
 890                     new Sorter<char[]>(a, bits | 1, upper + 1, high),
 891                     new Sorter<char[]>(a, bits, low, lower)
 892                 );
 893             } else {
 894                 sort(a, bits | 1, false, upper + 1, high);
 895                 sort(a, bits, false, low, lower);
 896                 sort(a, bits | 1, false, lower + 1, upper);
 897             }
 898         } else { // Partitioning with one pivot
 899 
 900             /*
 901              * Use the third element as the pivot. This value
 902              * is inexpensive approximation of the median.
 903              */
 904             char pivot = a[e3];
 905 
 906             /*
 907              * The first element to be sorted is moved to the location
 908              * formerly occupied by the pivot. When partitioning is
 909              * completed, the pivot is swapped back into its final
 910              * position, and excluded from subsequent sorting.
 911              */
 912             a[e3] = a[lower];
 913 
 914             /*
 915              * Traditional 3-way (Dutch National Flag) partitioning
 916              *
 917              *   left part                 central part    right part
 918              * +------------------------------------------------------+
 919              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
 920              * +------------------------------------------------------+
 921              *              ^           ^                ^
 922              *              |           |                |
 923              *            lower         k              upper
 924              *
 925              * Invariants:
 926              *
 927              *   all in (low, lower] < pivot
 928              *   all in (k, upper)  == pivot
 929              *   all in [upper, end] > pivot
 930              *
 931              * Pointer k is the last index of ?-part
 932              */
 933             for (int k = ++upper; --k > lower; ) {
 934                 if (a[k] == pivot) {
 935                     continue;
 936                 }
 937                 char ak = a[k];
 938 
 939                 if (ak < pivot) { // Move a[k] to the left side
 940                     while (a[++lower] < pivot);
 941 
 942                     if (lower > k) {
 943                         lower = k;
 944                         break;
 945                     }
 946                     a[k] = pivot;
 947 
 948                     if (a[lower] > pivot) {
 949                         a[--upper] = a[lower];
 950                     }
 951                     a[lower] = ak;
 952                 } else { // ak > pivot - Move a[k] to the right side
 953                     a[k] = pivot;
 954                     a[--upper] = ak;
 955                 }
 956             }
 957 
 958             /*
 959              * Swap the pivot into its final position.
 960              */
 961             a[low] = a[lower]; a[lower] = pivot;
 962 
 963             /*
 964              * Sort the left and the right parts recursively, excluding
 965              * known pivot. All elements from the central part are equal
 966              * and, therefore, already sorted.
 967              */
 968             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
 969                 ForkJoinTask.invokeAll(
 970                     new Sorter<char[]>(a, bits, low, lower),
 971                     new Sorter<char[]>(a, bits | 1, upper, high)
 972                 );
 973             } else {
 974                 sort(a, bits | 1, false, upper, high);
 975                 sort(a, bits, false, low, lower);
 976             }
 977         }
 978     }
 979 
 980     /**
 981      * Sorts the specified range of the array.
 982      *
 983      * @param a the array to be sorted
 984      * @param parallel indicates whether sorting is performed in parallel
 985      * @param low the index of the first element, inclusive, to be sorted
 986      * @param high the index of the last element, exclusive, to be sorted
 987      */
 988     static void sort(short[] a, boolean parallel, int low, int high) {
 989         if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
 990             SortingAlgorithms.countingSort(a, low, high);
 991         } else {
 992             sort(a, LEFTMOST_BITS, parallel, low, high);
 993         }
 994     }
 995 
 996     /**
 997      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
 998      *
 999      * @param a the array to be sorted
1000      * @param bits the recursion depth of Quicksort and the leftmost flag
1001      * @param parallel indicates whether sorting is performed in parallel
1002      * @param low the index of the first element, inclusive, to be sorted
1003      * @param high the index of the last element, exclusive, to be sorted
1004      */
1005     private static void sort(short[] a, int bits, boolean parallel, int low, int high) {
1006         int end = high - 1, length = high - low;
1007 
1008         /*
1009          * Run insertion sorts on non-leftmost part.
1010          */
1011         if ((bits & 1) > 0) {
1012 
1013             /*
1014              * Use nano insertion sort on tiny part.
1015              */
1016             if (length < NANO_INSERTION_SORT_THRESHOLD) {
1017                 SortingAlgorithms.nanoInsertionSort(a, low, high);
1018                 return;
1019             }
1020 
1021             /*
1022              * Use pair insertion sort on small part.
1023              */
1024             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
1025                 SortingAlgorithms.pairInsertionSort(a, low, end);
1026                 return;
1027             }
1028         }
1029 
1030         /*
1031          * Switch to heap sort on the leftmost part or
1032          * if the execution time is becoming quadratic.
1033          */
1034         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
1035             SortingAlgorithms.heapSort(a, low, end);
1036             return;
1037         }
1038 
1039         /*
1040          * Check if the array is nearly sorted
1041          * and then try to sort it by Merging sort.
1042          */
1043         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
1044             return;
1045         }
1046 
1047         /*
1048          * The splitting of the array, defined by the following
1049          * step, is related to the inexpensive approximation of
1050          * the golden ratio.
1051          */
1052         int step = (length >> 3) * 3 + 3;
1053 
1054         /*
1055          * Five elements around (and including) the central element in
1056          * the array will be used for pivot selection as described below.
1057          * The unequal choice of spacing these elements was empirically
1058          * determined to work well on a wide variety of inputs.
1059          */
1060         int e1 = low + step;
1061         int e5 = end - step;
1062         int e3 = (e1 + e5) >>> 1;
1063         int e2 = (e1 + e3) >>> 1;
1064         int e4 = (e3 + e5) >>> 1;
1065 
1066         /*
1067          * Sort these elements in place by the combination
1068          * of 5-element sorting network and insertion sort.
1069          */
1070         if (a[e5] < a[e3]) { short t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
1071         if (a[e4] < a[e2]) { short t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
1072         if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
1073         if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
1074         if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
1075 
1076         if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t;
1077             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
1078                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
1079                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
1080                 }
1081             }
1082         }
1083 
1084         // Pointers
1085         int lower = low; // The index of the last element of the left part
1086         int upper = end; // The index of the first element of the right part
1087 
1088         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
1089 
1090             /*
1091              * Use the first and the fifth elements as the pivots.
1092              * These values are inexpensive approximation of tertiles.
1093              * Note, that pivot1 < pivot2.
1094              */
1095             short pivot1 = a[e1];
1096             short pivot2 = a[e5];
1097 
1098             /*
1099              * The first and the last elements to be sorted are moved to the
1100              * locations formerly occupied by the pivots. When partitioning
1101              * is completed, the pivots are swapped back into their final
1102              * positions, and excluded from subsequent sorting.
1103              */
1104             a[e1] = a[lower];
1105             a[e5] = a[upper];
1106 
1107             /*
1108              * Skip elements, which are less or greater than the pivots.
1109              */
1110             while (a[++lower] < pivot1);
1111             while (a[--upper] > pivot2);
1112 
1113             /*
1114              * Backwards 3-interval partitioning
1115              *
1116              *   left part                 central part          right part
1117              * +------------------------------------------------------------+
1118              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
1119              * +------------------------------------------------------------+
1120              *             ^       ^                            ^
1121              *             |       |                            |
1122              *           lower     k                          upper
1123              *
1124              * Invariants:
1125              *
1126              *              all in (low, lower] < pivot1
1127              *    pivot1 <= all in (k, upper)  <= pivot2
1128              *              all in [upper, end) > pivot2
1129              *
1130              * Pointer k is the last index of ?-part
1131              */
1132             for (int $ = --lower, k = ++upper; --k > lower; ) {
1133                 short ak = a[k];
1134 
1135                 if (ak < pivot1) { // Move a[k] to the left side
1136                     while (a[++lower] < pivot1);
1137 
1138                     if (lower > k) {
1139                         lower = k;
1140                         break;
1141                     }
1142                     if (a[lower] > pivot2) { // a[lower] >= pivot1
1143                         a[k] = a[--upper];
1144                         a[upper] = a[lower];
1145                     } else { // pivot1 <= a[lower] <= pivot2
1146                         a[k] = a[lower];
1147                     }
1148                     a[lower] = ak;
1149                 } else if (ak > pivot2) { // Move a[k] to the right side
1150                     a[k] = a[--upper];
1151                     a[upper] = ak;
1152                 }
1153             }
1154 
1155             /*
1156              * Swap the pivots into their final positions.
1157              */
1158             a[low] = a[lower]; a[lower] = pivot1;
1159             a[end] = a[upper]; a[upper] = pivot2;
1160 
1161             /*
1162              * Sort all parts recursively, excluding known pivots.
1163              */
1164             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1165                 ForkJoinTask.invokeAll(
1166                     new Sorter<short[]>(a, bits | 1, lower + 1, upper),
1167                     new Sorter<short[]>(a, bits | 1, upper + 1, high),
1168                     new Sorter<short[]>(a, bits, low, lower)
1169                 );
1170             } else {
1171                 sort(a, bits | 1, false, upper + 1, high);
1172                 sort(a, bits, false, low, lower);
1173                 sort(a, bits | 1, false, lower + 1, upper);
1174             }
1175         } else { // Partitioning with one pivot
1176 
1177             /*
1178              * Use the third element as the pivot. This value
1179              * is inexpensive approximation of the median.
1180              */
1181             short pivot = a[e3];
1182 
1183             /*
1184              * The first element to be sorted is moved to the location
1185              * formerly occupied by the pivot. When partitioning is
1186              * completed, the pivot is swapped back into its final
1187              * position, and excluded from subsequent sorting.
1188              */
1189             a[e3] = a[lower];
1190 
1191             /*
1192              * Traditional 3-way (Dutch National Flag) partitioning
1193              *
1194              *   left part                 central part    right part
1195              * +------------------------------------------------------+
1196              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
1197              * +------------------------------------------------------+
1198              *              ^           ^                ^
1199              *              |           |                |
1200              *            lower         k              upper
1201              *
1202              * Invariants:
1203              *
1204              *   all in (low, lower] < pivot
1205              *   all in (k, upper)  == pivot
1206              *   all in [upper, end] > pivot
1207              *
1208              * Pointer k is the last index of ?-part
1209              */
1210             for (int k = ++upper; --k > lower; ) {
1211                 if (a[k] == pivot) {
1212                     continue;
1213                 }
1214                 short ak = a[k];
1215 
1216                 if (ak < pivot) { // Move a[k] to the left side
1217                     while (a[++lower] < pivot);
1218 
1219                     if (lower > k) {
1220                         lower = k;
1221                         break;
1222                     }
1223                     a[k] = pivot;
1224 
1225                     if (a[lower] > pivot) {
1226                         a[--upper] = a[lower];
1227                     }
1228                     a[lower] = ak;
1229                 } else { // ak > pivot - Move a[k] to the right side
1230                     a[k] = pivot;
1231                     a[--upper] = ak;
1232                 }
1233             }
1234 
1235             /*
1236              * Swap the pivot into its final position.
1237              */
1238             a[low] = a[lower]; a[lower] = pivot;
1239 
1240             /*
1241              * Sort the left and the right parts recursively, excluding
1242              * known pivot. All elements from the central part are equal
1243              * and, therefore, already sorted.
1244              */
1245             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1246                 ForkJoinTask.invokeAll(
1247                     new Sorter<short[]>(a, bits, low, lower),
1248                     new Sorter<short[]>(a, bits | 1, upper, high)
1249                 );
1250             } else {
1251                 sort(a, bits | 1, false, upper, high);
1252                 sort(a, bits, false, low, lower);
1253             }
1254         }
1255     }
1256 
1257     /**
1258      * Sorts the specified range of the array.
1259      *
1260      * @param a the array to be sorted
1261      * @param parallel indicates whether sorting is performed in parallel
1262      * @param low the index of the first element, inclusive, to be sorted
1263      * @param high the index of the last element, exclusive, to be sorted
1264      */
1265     static void sort(float[] a, boolean parallel, int low, int high) {
1266         /*
1267          * Phase 1. Count the number of negative zero -0.0f,
1268          * turn them into positive zero, and move all NaNs
1269          * to the end of the array.
1270          */
1271         int numNegativeZero = 0;
1272 
1273         for (int k = high; k > low; ) {
1274             float ak = a[--k];
1275 
1276             if (ak == 0.0f && Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
1277                 numNegativeZero += 1;
1278                 a[k] = 0.0f;
1279             } else if (ak != ak) { // ak is NaN
1280                 a[k] = a[--high];
1281                 a[high] = ak;
1282             }
1283         }
1284 
1285         /*
1286          * Phase 2. Sort everything except NaNs,
1287          * which are already in place.
1288          */
1289         sort(a, LEFTMOST_BITS, parallel, low, high);
1290 
1291         /*
1292          * Phase 3. Turn positive zero 0.0f
1293          * back into negative zero -0.0f.
1294          */
1295         if (++numNegativeZero == 1) {
1296             return;
1297         }
1298 
1299         /*
1300          * Find the position one less than
1301          * the index of the first zero.
1302          */
1303         while (low <= high) {
1304             int middle = (low + high) >>> 1;
1305 
1306             if (a[middle] < 0) {
1307                 low = middle + 1;
1308             } else {
1309                 high = middle - 1;
1310             }
1311         }
1312 
1313         /*
1314          * Replace the required number of 0.0f by -0.0f.
1315          */
1316         while (--numNegativeZero > 0) {
1317             a[++high] = -0.0f;
1318         }
1319     }
1320 
1321     /**
1322      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
1323      *
1324      * @param a the array to be sorted
1325      * @param bits the recursion depth of Quicksort and the leftmost flag
1326      * @param parallel indicates whether sorting is performed in parallel
1327      * @param low the index of the first element, inclusive, to be sorted
1328      * @param high the index of the last element, exclusive, to be sorted
1329      */
1330     private static void sort(float[] a, int bits, boolean parallel, int low, int high) {
1331         int end = high - 1, length = high - low;
1332 
1333         /*
1334          * Run insertion sorts on non-leftmost part.
1335          */
1336         if ((bits & 1) > 0) {
1337 
1338             /*
1339              * Use nano insertion sort on tiny part.
1340              */
1341             if (length < NANO_INSERTION_SORT_THRESHOLD) {
1342                 SortingAlgorithms.nanoInsertionSort(a, low, high);
1343                 return;
1344             }
1345 
1346             /*
1347              * Use pair insertion sort on small part.
1348              */
1349             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
1350                 SortingAlgorithms.pairInsertionSort(a, low, end);
1351                 return;
1352             }
1353         }
1354 
1355         /*
1356          * Switch to heap sort on the leftmost part or
1357          * if the execution time is becoming quadratic.
1358          */
1359         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
1360             SortingAlgorithms.heapSort(a, low, end);
1361             return;
1362         }
1363 
1364         /*
1365          * Check if the array is nearly sorted
1366          * and then try to sort it by Merging sort.
1367          */
1368         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
1369             return;
1370         }
1371 
1372         /*
1373          * The splitting of the array, defined by the following
1374          * step, is related to the inexpensive approximation of
1375          * the golden ratio.
1376          */
1377         int step = (length >> 3) * 3 + 3;
1378 
1379         /*
1380          * Five elements around (and including) the central element in
1381          * the array will be used for pivot selection as described below.
1382          * The unequal choice of spacing these elements was empirically
1383          * determined to work well on a wide variety of inputs.
1384          */
1385         int e1 = low + step;
1386         int e5 = end - step;
1387         int e3 = (e1 + e5) >>> 1;
1388         int e2 = (e1 + e3) >>> 1;
1389         int e4 = (e3 + e5) >>> 1;
1390 
1391         /*
1392          * Sort these elements in place by the combination
1393          * of 5-element sorting network and insertion sort.
1394          */
1395         if (a[e5] < a[e3]) { float t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
1396         if (a[e4] < a[e2]) { float t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
1397         if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
1398         if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
1399         if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
1400 
1401         if (a[e1] > a[e2]) { float t = a[e1]; a[e1] = a[e2]; a[e2] = t;
1402             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
1403                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
1404                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
1405                 }
1406             }
1407         }
1408 
1409         // Pointers
1410         int lower = low; // The index of the last element of the left part
1411         int upper = end; // The index of the first element of the right part
1412 
1413         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
1414 
1415             /*
1416              * Use the first and the fifth elements as the pivots.
1417              * These values are inexpensive approximation of tertiles.
1418              * Note, that pivot1 < pivot2.
1419              */
1420             float pivot1 = a[e1];
1421             float pivot2 = a[e5];
1422 
1423             /*
1424              * The first and the last elements to be sorted are moved to the
1425              * locations formerly occupied by the pivots. When partitioning
1426              * is completed, the pivots are swapped back into their final
1427              * positions, and excluded from subsequent sorting.
1428              */
1429             a[e1] = a[lower];
1430             a[e5] = a[upper];
1431 
1432             /*
1433              * Skip elements, which are less or greater than the pivots.
1434              */
1435             while (a[++lower] < pivot1);
1436             while (a[--upper] > pivot2);
1437 
1438             /*
1439              * Backwards 3-interval partitioning
1440              *
1441              *   left part                 central part          right part
1442              * +------------------------------------------------------------+
1443              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
1444              * +------------------------------------------------------------+
1445              *             ^       ^                            ^
1446              *             |       |                            |
1447              *           lower     k                          upper
1448              *
1449              * Invariants:
1450              *
1451              *              all in (low, lower] < pivot1
1452              *    pivot1 <= all in (k, upper)  <= pivot2
1453              *              all in [upper, end) > pivot2
1454              *
1455              * Pointer k is the last index of ?-part
1456              */
1457             for (int $ = --lower, k = ++upper; --k > lower; ) {
1458                 float ak = a[k];
1459 
1460                 if (ak < pivot1) { // Move a[k] to the left side
1461                     while (a[++lower] < pivot1);
1462 
1463                     if (lower > k) {
1464                         lower = k;
1465                         break;
1466                     }
1467                     if (a[lower] > pivot2) { // a[lower] >= pivot1
1468                         a[k] = a[--upper];
1469                         a[upper] = a[lower];
1470                     } else { // pivot1 <= a[lower] <= pivot2
1471                         a[k] = a[lower];
1472                     }
1473                     a[lower] = ak;
1474                 } else if (ak > pivot2) { // Move a[k] to the right side
1475                     a[k] = a[--upper];
1476                     a[upper] = ak;
1477                 }
1478             }
1479 
1480             /*
1481              * Swap the pivots into their final positions.
1482              */
1483             a[low] = a[lower]; a[lower] = pivot1;
1484             a[end] = a[upper]; a[upper] = pivot2;
1485 
1486             /*
1487              * Sort all parts recursively, excluding known pivots.
1488              */
1489             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1490                 ForkJoinTask.invokeAll(
1491                     new Sorter<float[]>(a, bits | 1, lower + 1, upper),
1492                     new Sorter<float[]>(a, bits | 1, upper + 1, high),
1493                     new Sorter<float[]>(a, bits, low, lower)
1494                 );
1495             } else {
1496                 sort(a, bits | 1, false, upper + 1, high);
1497                 sort(a, bits, false, low, lower);
1498                 sort(a, bits | 1, false, lower + 1, upper);
1499             }
1500         } else { // Partitioning with one pivot
1501 
1502             /*
1503              * Use the third element as the pivot. This value
1504              * is inexpensive approximation of the median.
1505              */
1506             float pivot = a[e3];
1507 
1508             /*
1509              * The first element to be sorted is moved to the location
1510              * formerly occupied by the pivot. When partitioning is
1511              * completed, the pivot is swapped back into its final
1512              * position, and excluded from subsequent sorting.
1513              */
1514             a[e3] = a[lower];
1515 
1516             /*
1517              * Traditional 3-way (Dutch National Flag) partitioning
1518              *
1519              *   left part                 central part    right part
1520              * +------------------------------------------------------+
1521              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
1522              * +------------------------------------------------------+
1523              *              ^           ^                ^
1524              *              |           |                |
1525              *            lower         k              upper
1526              *
1527              * Invariants:
1528              *
1529              *   all in (low, lower] < pivot
1530              *   all in (k, upper)  == pivot
1531              *   all in [upper, end] > pivot
1532              *
1533              * Pointer k is the last index of ?-part
1534              */
1535             for (int k = ++upper; --k > lower; ) {
1536                 if (a[k] == pivot) {
1537                     continue;
1538                 }
1539                 float ak = a[k];
1540 
1541                 if (ak < pivot) { // Move a[k] to the left side
1542                     while (a[++lower] < pivot);
1543 
1544                     if (lower > k) {
1545                         lower = k;
1546                         break;
1547                     }
1548                     a[k] = pivot;
1549 
1550                     if (a[lower] > pivot) {
1551                         a[--upper] = a[lower];
1552                     }
1553                     a[lower] = ak;
1554                 } else { // ak > pivot - Move a[k] to the right side
1555                     a[k] = pivot;
1556                     a[--upper] = ak;
1557                 }
1558             }
1559 
1560             /*
1561              * Swap the pivot into its final position.
1562              */
1563             a[low] = a[lower]; a[lower] = pivot;
1564 
1565             /*
1566              * Sort the left and the right parts recursively, excluding
1567              * known pivot. All elements from the central part are equal
1568              * and, therefore, already sorted.
1569              */
1570             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1571                 ForkJoinTask.invokeAll(
1572                     new Sorter<float[]>(a, bits, low, lower),
1573                     new Sorter<float[]>(a, bits | 1, upper, high)
1574                 );
1575             } else {
1576                 sort(a, bits | 1, false, upper, high);
1577                 sort(a, bits, false, low, lower);
1578             }
1579         }
1580     }
1581 
1582     /**
1583      * Sorts the specified range of the array.
1584      *
1585      * @param a the array to be sorted
1586      * @param parallel indicates whether sorting is performed in parallel
1587      * @param low the index of the first element, inclusive, to be sorted
1588      * @param high the index of the last element, exclusive, to be sorted
1589      */
1590     static void sort(double[] a, boolean parallel, int low, int high) {
1591         /*
1592          * Phase 1. Count the number of negative zero -0.0d,
1593          * turn them into positive zero, and move all NaNs
1594          * to the end of the array.
1595          */
1596         int numNegativeZero = 0;
1597 
1598         for (int k = high; k > low; ) {
1599             double ak = a[--k];
1600 
1601             if (ak == 0.0d && Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
1602                 numNegativeZero += 1;
1603                 a[k] = 0.0d;
1604             } else if (ak != ak) { // ak is NaN
1605                 a[k] = a[--high];
1606                 a[high] = ak;
1607             }
1608         }
1609 
1610         /*
1611          * Phase 2. Sort everything except NaNs,
1612          * which are already in place.
1613          */
1614         sort(a, LEFTMOST_BITS, parallel, low, high);
1615 
1616         /*
1617          * Phase 3. Turn positive zero 0.0d
1618          * back into negative zero -0.0d.
1619          */
1620         if (++numNegativeZero == 1) {
1621             return;
1622         }
1623 
1624         /*
1625          * Find the position one less than
1626          * the index of the first zero.
1627          */
1628         while (low <= high) {
1629             int middle = (low + high) >>> 1;
1630 
1631             if (a[middle] < 0) {
1632                 low = middle + 1;
1633             } else {
1634                 high = middle - 1;
1635             }
1636         }
1637 
1638         /*
1639          * Replace the required number of 0.0d by -0.0d.
1640          */
1641         while (--numNegativeZero > 0) {
1642             a[++high] = -0.0d;
1643         }
1644     }
1645 
1646     /**
1647      * Sorts the specified range of the array by the Dual-Pivot Quicksort.
1648      *
1649      * @param a the array to be sorted
1650      * @param bits the recursion depth of Quicksort and the leftmost flag
1651      * @param parallel indicates whether sorting is performed in parallel
1652      * @param low the index of the first element, inclusive, to be sorted
1653      * @param high the index of the last element, exclusive, to be sorted
1654      */
1655     private static void sort(double[] a, int bits, boolean parallel, int low, int high) {
1656         int end = high - 1, length = high - low;
1657 
1658         /*
1659          * Run insertion sorts on non-leftmost part.
1660          */
1661         if ((bits & 1) > 0) {
1662 
1663             /*
1664              * Use nano insertion sort on tiny part.
1665              */
1666             if (length < NANO_INSERTION_SORT_THRESHOLD) {
1667                 SortingAlgorithms.nanoInsertionSort(a, low, high);
1668                 return;
1669             }
1670 
1671             /*
1672              * Use pair insertion sort on small part.
1673              */
1674             if (length < PAIR_INSERTION_SORT_THRESHOLD) {
1675                 SortingAlgorithms.pairInsertionSort(a, low, end);
1676                 return;
1677             }
1678         }
1679 
1680         /*
1681          * Switch to heap sort on the leftmost part or
1682          * if the execution time is becoming quadratic.
1683          */
1684         if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
1685             SortingAlgorithms.heapSort(a, low, end);
1686             return;
1687         }
1688 
1689         /*
1690          * Check if the array is nearly sorted
1691          * and then try to sort it by Merging sort.
1692          */
1693         if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
1694             return;
1695         }
1696 
1697         /*
1698          * The splitting of the array, defined by the following
1699          * step, is related to the inexpensive approximation of
1700          * the golden ratio.
1701          */
1702         int step = (length >> 3) * 3 + 3;
1703 
1704         /*
1705          * Five elements around (and including) the central element in
1706          * the array will be used for pivot selection as described below.
1707          * The unequal choice of spacing these elements was empirically
1708          * determined to work well on a wide variety of inputs.
1709          */
1710         int e1 = low + step;
1711         int e5 = end - step;
1712         int e3 = (e1 + e5) >>> 1;
1713         int e2 = (e1 + e3) >>> 1;
1714         int e4 = (e3 + e5) >>> 1;
1715 
1716         /*
1717          * Sort these elements in place by the combination
1718          * of 5-element sorting network and insertion sort.
1719          */
1720         if (a[e5] < a[e3]) { double t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
1721         if (a[e4] < a[e2]) { double t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
1722         if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
1723         if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
1724         if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t; }
1725 
1726         if (a[e1] > a[e2]) { double t = a[e1]; a[e1] = a[e2]; a[e2] = t;
1727             if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
1728                 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
1729                     if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
1730                 }
1731             }
1732         }
1733 
1734         // Pointers
1735         int lower = low; // The index of the last element of the left part
1736         int upper = end; // The index of the first element of the right part
1737 
1738         if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
1739 
1740             /*
1741              * Use the first and the fifth elements as the pivots.
1742              * These values are inexpensive approximation of tertiles.
1743              * Note, that pivot1 < pivot2.
1744              */
1745             double pivot1 = a[e1];
1746             double pivot2 = a[e5];
1747 
1748             /*
1749              * The first and the last elements to be sorted are moved to the
1750              * locations formerly occupied by the pivots. When partitioning
1751              * is completed, the pivots are swapped back into their final
1752              * positions, and excluded from subsequent sorting.
1753              */
1754             a[e1] = a[lower];
1755             a[e5] = a[upper];
1756 
1757             /*
1758              * Skip elements, which are less or greater than the pivots.
1759              */
1760             while (a[++lower] < pivot1);
1761             while (a[--upper] > pivot2);
1762 
1763             /*
1764              * Backwards 3-interval partitioning
1765              *
1766              *   left part                 central part          right part
1767              * +------------------------------------------------------------+
1768              * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
1769              * +------------------------------------------------------------+
1770              *             ^       ^                            ^
1771              *             |       |                            |
1772              *           lower     k                          upper
1773              *
1774              * Invariants:
1775              *
1776              *              all in (low, lower] < pivot1
1777              *    pivot1 <= all in (k, upper)  <= pivot2
1778              *              all in [upper, end) > pivot2
1779              *
1780              * Pointer k is the last index of ?-part
1781              */
1782             for (int $ = --lower, k = ++upper; --k > lower; ) {
1783                 double ak = a[k];
1784 
1785                 if (ak < pivot1) { // Move a[k] to the left side
1786                     while (a[++lower] < pivot1);
1787 
1788                     if (lower > k) {
1789                         lower = k;
1790                         break;
1791                     }
1792                     if (a[lower] > pivot2) { // a[lower] >= pivot1
1793                         a[k] = a[--upper];
1794                         a[upper] = a[lower];
1795                     } else { // pivot1 <= a[lower] <= pivot2
1796                         a[k] = a[lower];
1797                     }
1798                     a[lower] = ak;
1799                 } else if (ak > pivot2) { // Move a[k] to the right side
1800                     a[k] = a[--upper];
1801                     a[upper] = ak;
1802                 }
1803             }
1804 
1805             /*
1806              * Swap the pivots into their final positions.
1807              */
1808             a[low] = a[lower]; a[lower] = pivot1;
1809             a[end] = a[upper]; a[upper] = pivot2;
1810 
1811             /*
1812              * Sort all parts recursively, excluding known pivots.
1813              */
1814             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1815                 ForkJoinTask.invokeAll(
1816                     new Sorter<double[]>(a, bits | 1, lower + 1, upper),
1817                     new Sorter<double[]>(a, bits | 1, upper + 1, high),
1818                     new Sorter<double[]>(a, bits, low, lower)
1819                 );
1820             } else {
1821                 sort(a, bits | 1, false, upper + 1, high);
1822                 sort(a, bits, false, low, lower);
1823                 sort(a, bits | 1, false, lower + 1, upper);
1824             }
1825         } else { // Partitioning with one pivot
1826 
1827             /*
1828              * Use the third element as the pivot. This value
1829              * is inexpensive approximation of the median.
1830              */
1831             double pivot = a[e3];
1832 
1833             /*
1834              * The first element to be sorted is moved to the location
1835              * formerly occupied by the pivot. When partitioning is
1836              * completed, the pivot is swapped back into its final
1837              * position, and excluded from subsequent sorting.
1838              */
1839             a[e3] = a[lower];
1840 
1841             /*
1842              * Traditional 3-way (Dutch National Flag) partitioning
1843              *
1844              *   left part                 central part    right part
1845              * +------------------------------------------------------+
1846              * |   < pivot   |     ?     |   == pivot   |   > pivot   |
1847              * +------------------------------------------------------+
1848              *              ^           ^                ^
1849              *              |           |                |
1850              *            lower         k              upper
1851              *
1852              * Invariants:
1853              *
1854              *   all in (low, lower] < pivot
1855              *   all in (k, upper)  == pivot
1856              *   all in [upper, end] > pivot
1857              *
1858              * Pointer k is the last index of ?-part
1859              */
1860             for (int k = ++upper; --k > lower; ) {
1861                 if (a[k] == pivot) {
1862                     continue;
1863                 }
1864                 double ak = a[k];
1865 
1866                 if (ak < pivot) { // Move a[k] to the left side
1867                     while (a[++lower] < pivot);
1868 
1869                     if (lower > k) {
1870                         lower = k;
1871                         break;
1872                     }
1873                     a[k] = pivot;
1874 
1875                     if (a[lower] > pivot) {
1876                         a[--upper] = a[lower];
1877                     }
1878                     a[lower] = ak;
1879                 } else { // ak > pivot - Move a[k] to the right side
1880                     a[k] = pivot;
1881                     a[--upper] = ak;
1882                 }
1883             }
1884 
1885             /*
1886              * Swap the pivot into its final position.
1887              */
1888             a[low] = a[lower]; a[lower] = pivot;
1889 
1890             /*
1891              * Sort the left and the right parts recursively, excluding
1892              * known pivot. All elements from the central part are equal
1893              * and, therefore, already sorted.
1894              */
1895             if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
1896                 ForkJoinTask.invokeAll(
1897                     new Sorter<double[]>(a, bits, low, lower),
1898                     new Sorter<double[]>(a, bits | 1, upper, high)
1899                 );
1900             } else {
1901                 sort(a, bits | 1, false, upper, high);
1902                 sort(a, bits, false, low, lower);
1903             }
1904         }
1905     }
1906 }