Home | History | Annotate | Download | only in util
      1 /*
      2  *  Licensed to the Apache Software Foundation (ASF) under one or more
      3  *  contributor license agreements. See the NOTICE file distributed with
      4  *  this work for additional information regarding copyright ownership.
      5  *  The ASF licenses this file to You under the Apache License, Version 2.0
      6  *  (the "License"); you may not use this file except in compliance with
      7  *  the License. You may obtain a copy of the License at
      8  *
      9  *     http://www.apache.org/licenses/LICENSE-2.0
     10  *
     11  *  Unless required by applicable law or agreed to in writing, software
     12  *  distributed under the License is distributed on an "AS IS" BASIS,
     13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14  *  See the License for the specific language governing permissions and
     15  *  limitations under the License.
     16  */
     17 
     18 package java.util;
     19 
     20 /**
     21  * This class implements the Dual-Pivot Quicksort algorithm by
     22  * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
     23  * offers O(n log(n)) performance on many data sets that cause other
     24  * quicksorts to degrade to quadratic performance, and is typically
     25  * faster than traditional (one-pivot) Quicksort implementations.
     26  *
     27  * @author Vladimir Yaroslavskiy
     28  * @author Jon Bentley
     29  * @author Josh Bloch
     30  *
     31  * @version 2009.11.29 m765.827.12i
     32  */
     33 final class DualPivotQuicksort {
     34 
     35     /**
     36      * Prevents instantiation.
     37      */
     38     private DualPivotQuicksort() {}
     39 
     40     /*
     41      * Tuning parameters.
     42      */
     43 
     44     /**
     45      * If the length of an array to be sorted is less than this
     46      * constant, insertion sort is used in preference to Quicksort.
     47      */
     48     private static final int INSERTION_SORT_THRESHOLD = 32;
     49 
     50     /**
     51      * If the length of a byte array to be sorted is greater than
     52      * this constant, counting sort is used in preference to Quicksort.
     53      */
     54     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
     55 
     56     /**
     57      * If the length of a short or char array to be sorted is greater
     58      * than this constant, counting sort is used in preference to Quicksort.
     59      */
     60     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
     61 
     62     /*
     63      * Sorting methods for 7 primitive types.
     64      */
     65 
     66     /**
     67      * Sorts the specified array into ascending numerical order.
     68      *
     69      * @param a the array to be sorted
     70      */
     71     public static void sort(int[] a) {
     72         doSort(a, 0, a.length - 1);
     73     }
     74 
     75     /**
     76      * Sorts the specified range of the array into ascending order. The range
     77      * to be sorted extends from the index {@code fromIndex}, inclusive, to
     78      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
     79      * the range to be sorted is empty (and the call is a no-op).
     80      *
     81      * @param a the array to be sorted
     82      * @param fromIndex the index of the first element, inclusive, to be sorted
     83      * @param toIndex the index of the last element, exclusive, to be sorted
     84      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
     85      * @throws ArrayIndexOutOfBoundsException
     86      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
     87      */
     88     public static void sort(int[] a, int fromIndex, int toIndex) {
     89         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
     90         doSort(a, fromIndex, toIndex - 1);
     91     }
     92 
     93     /**
     94      * Sorts the specified range of the array into ascending order. This
     95      * method differs from the public {@code sort} method in that the
     96      * {@code right} index is inclusive, and it does no range checking
     97      * on {@code left} or {@code right}.
     98      *
     99      * @param a the array to be sorted
    100      * @param left the index of the first element, inclusive, to be sorted
    101      * @param right the index of the last element, inclusive, to be sorted
    102      */
    103     private static void doSort(int[] a, int left, int right) {
    104         // Use insertion sort on tiny arrays
    105         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
    106             for (int i = left + 1; i <= right; i++) {
    107                 int ai = a[i];
    108                 int j;
    109                 for (j = i - 1; j >= left && ai < a[j]; j--) {
    110                     a[j + 1] = a[j];
    111                 }
    112                 a[j + 1] = ai;
    113             }
    114         } else { // Use Dual-Pivot Quicksort on large arrays
    115             dualPivotQuicksort(a, left, right);
    116         }
    117     }
    118 
    119     /**
    120      * Sorts the specified range of the array into ascending order by the
    121      * Dual-Pivot Quicksort algorithm.
    122      *
    123      * @param a the array to be sorted
    124      * @param left the index of the first element, inclusive, to be sorted
    125      * @param right the index of the last element, inclusive, to be sorted
    126      */
    127     private static void dualPivotQuicksort(int[] a, int left, int right) {
    128         // Compute indices of five evenly spaced elements
    129         int sixth = (right - left + 1) / 6;
    130         int e1 = left  + sixth;
    131         int e5 = right - sixth;
    132         int e3 = (left + right) >>> 1; // The midpoint
    133         int e4 = e3 + sixth;
    134         int e2 = e3 - sixth;
    135 
    136         // Sort these elements using a 5-element sorting network
    137         int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
    138 
    139         if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
    140         if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
    141         if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
    142         if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
    143         if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
    144         if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
    145         if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
    146         if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
    147         if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
    148 
    149         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
    150 
    151         /*
    152          * Use the second and fourth of the five sorted elements as pivots.
    153          * These values are inexpensive approximations of the first and
    154          * second terciles of the array. Note that pivot1 <= pivot2.
    155          *
    156          * The pivots are stored in local variables, and the first and
    157          * the last of the elements to be sorted are moved to the locations
    158          * formerly occupied by the pivots. When partitioning is complete,
    159          * the pivots are swapped back into their final positions, and
    160          * excluded from subsequent sorting.
    161          */
    162         int pivot1 = ae2; a[e2] = a[left];
    163         int pivot2 = ae4; a[e4] = a[right];
    164 
    165         // Pointers
    166         int less  = left  + 1; // The index of first element of center part
    167         int great = right - 1; // The index before first element of right part
    168 
    169         boolean pivotsDiffer = (pivot1 != pivot2);
    170 
    171         if (pivotsDiffer) {
    172             /*
    173              * Partitioning:
    174              *
    175              *   left part         center part                    right part
    176              * +------------------------------------------------------------+
    177              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
    178              * +------------------------------------------------------------+
    179              *              ^                          ^       ^
    180              *              |                          |       |
    181              *             less                        k     great
    182              *
    183              * Invariants:
    184              *
    185              *              all in (left, less)   < pivot1
    186              *    pivot1 <= all in [less, k)     <= pivot2
    187              *              all in (great, right) > pivot2
    188              *
    189              * Pointer k is the first index of ?-part
    190              */
    191             outer:
    192             for (int k = less; k <= great; k++) {
    193                 int ak = a[k];
    194                 if (ak < pivot1) { // Move a[k] to left part
    195                     if (k != less) {
    196                         a[k] = a[less];
    197                         a[less] = ak;
    198                     }
    199                     less++;
    200                 } else if (ak > pivot2) { // Move a[k] to right part
    201                     while (a[great] > pivot2) {
    202                         if (great-- == k) {
    203                             break outer;
    204                         }
    205                     }
    206                     if (a[great] < pivot1) {
    207                         a[k] = a[less];
    208                         a[less++] = a[great];
    209                         a[great--] = ak;
    210                     } else { // pivot1 <= a[great] <= pivot2
    211                         a[k] = a[great];
    212                         a[great--] = ak;
    213                     }
    214                 }
    215             }
    216         } else { // Pivots are equal
    217             /*
    218              * Partition degenerates to the traditional 3-way,
    219              * or "Dutch National Flag", partition:
    220              *
    221              *   left part   center part            right part
    222              * +----------------------------------------------+
    223              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
    224              * +----------------------------------------------+
    225              *              ^            ^       ^
    226              *              |            |       |
    227              *             less          k     great
    228              *
    229              * Invariants:
    230              *
    231              *   all in (left, less)   < pivot
    232              *   all in [less, k)     == pivot
    233              *   all in (great, right) > pivot
    234              *
    235              * Pointer k is the first index of ?-part
    236              */
    237             for (int k = less; k <= great; k++) {
    238                 int ak = a[k];
    239                 if (ak == pivot1) {
    240                     continue;
    241                 }
    242                 if (ak < pivot1) { // Move a[k] to left part
    243                     if (k != less) {
    244                         a[k] = a[less];
    245                         a[less] = ak;
    246                     }
    247                     less++;
    248                 } else { // (a[k] > pivot1) -  Move a[k] to right part
    249                     /*
    250                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
    251                      * that great will still be >= k when the following loop
    252                      * terminates, even though we don't test for it explicitly.
    253                      * In other words, a[e3] acts as a sentinel for great.
    254                      */
    255                     while (a[great] > pivot1) {
    256                         great--;
    257                     }
    258                     if (a[great] < pivot1) {
    259                         a[k] = a[less];
    260                         a[less++] = a[great];
    261                         a[great--] = ak;
    262                     } else { // a[great] == pivot1
    263                         a[k] = pivot1;
    264                         a[great--] = ak;
    265                     }
    266                 }
    267             }
    268         }
    269 
    270         // Swap pivots into their final positions
    271         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    272         a[right] = a[great + 1]; a[great + 1] = pivot2;
    273 
    274         // Sort left and right parts recursively, excluding known pivot values
    275         doSort(a, left,   less - 2);
    276         doSort(a, great + 2, right);
    277 
    278         /*
    279          * If pivot1 == pivot2, all elements from center
    280          * part are equal and, therefore, already sorted
    281          */
    282         if (!pivotsDiffer) {
    283             return;
    284         }
    285 
    286         /*
    287          * If center part is too large (comprises > 2/3 of the array),
    288          * swap internal pivot values to ends
    289          */
    290         if (less < e1 && great > e5) {
    291             while (a[less] == pivot1) {
    292                 less++;
    293             }
    294             while (a[great] == pivot2) {
    295                 great--;
    296             }
    297 
    298             /*
    299              * Partitioning:
    300              *
    301              *   left part       center part                   right part
    302              * +----------------------------------------------------------+
    303              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
    304              * +----------------------------------------------------------+
    305              *              ^                        ^       ^
    306              *              |                        |       |
    307              *             less                      k     great
    308              *
    309              * Invariants:
    310              *
    311              *              all in (*, less)  == pivot1
    312              *     pivot1 < all in [less, k)   < pivot2
    313              *              all in (great, *) == pivot2
    314              *
    315              * Pointer k is the first index of ?-part
    316              */
    317             outer:
    318             for (int k = less; k <= great; k++) {
    319                 int ak = a[k];
    320                 if (ak == pivot2) { // Move a[k] to right part
    321                     while (a[great] == pivot2) {
    322                         if (great-- == k) {
    323                             break outer;
    324                         }
    325                     }
    326                     if (a[great] == pivot1) {
    327                         a[k] = a[less];
    328                         a[less++] = pivot1;
    329                     } else { // pivot1 < a[great] < pivot2
    330                         a[k] = a[great];
    331                     }
    332                     a[great--] = pivot2;
    333                 } else if (ak == pivot1) { // Move a[k] to left part
    334                     a[k] = a[less];
    335                     a[less++] = pivot1;
    336                 }
    337             }
    338         }
    339 
    340         // Sort center part recursively, excluding known pivot values
    341         doSort(a, less, great);
    342     }
    343 
    344     /**
    345      * Sorts the specified array into ascending numerical order.
    346      *
    347      * @param a the array to be sorted
    348      */
    349     public static void sort(long[] a) {
    350         doSort(a, 0, a.length - 1);
    351     }
    352 
    353     /**
    354      * Sorts the specified range of the array into ascending order. The range
    355      * to be sorted extends from the index {@code fromIndex}, inclusive, to
    356      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
    357      * the range to be sorted is empty (and the call is a no-op).
    358      *
    359      * @param a the array to be sorted
    360      * @param fromIndex the index of the first element, inclusive, to be sorted
    361      * @param toIndex the index of the last element, exclusive, to be sorted
    362      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
    363      * @throws ArrayIndexOutOfBoundsException
    364      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
    365      */
    366     public static void sort(long[] a, int fromIndex, int toIndex) {
    367         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
    368         doSort(a, fromIndex, toIndex - 1);
    369     }
    370 
    371     /**
    372      * Sorts the specified range of the array into ascending order. This
    373      * method differs from the public {@code sort} method in that the
    374      * {@code right} index is inclusive, and it does no range checking on
    375      * {@code left} or {@code right}.
    376      *
    377      * @param a the array to be sorted
    378      * @param left the index of the first element, inclusive, to be sorted
    379      * @param right the index of the last element, inclusive, to be sorted
    380      */
    381     private static void doSort(long[] a, int left, int right) {
    382         // Use insertion sort on tiny arrays
    383         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
    384             for (int i = left + 1; i <= right; i++) {
    385                 long ai = a[i];
    386                 int j;
    387                 for (j = i - 1; j >= left && ai < a[j]; j--) {
    388                     a[j + 1] = a[j];
    389                 }
    390                 a[j + 1] = ai;
    391             }
    392         } else { // Use Dual-Pivot Quicksort on large arrays
    393             dualPivotQuicksort(a, left, right);
    394         }
    395     }
    396 
    397     /**
    398      * Sorts the specified range of the array into ascending order by the
    399      * Dual-Pivot Quicksort algorithm.
    400      *
    401      * @param a the array to be sorted
    402      * @param left the index of the first element, inclusive, to be sorted
    403      * @param right the index of the last element, inclusive, to be sorted
    404      */
    405     private static void dualPivotQuicksort(long[] a, int left, int right) {
    406         // Compute indices of five evenly spaced elements
    407         int sixth = (right - left + 1) / 6;
    408         int e1 = left  + sixth;
    409         int e5 = right - sixth;
    410         int e3 = (left + right) >>> 1; // The midpoint
    411         int e4 = e3 + sixth;
    412         int e2 = e3 - sixth;
    413 
    414         // Sort these elements using a 5-element sorting network
    415         long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
    416 
    417         if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
    418         if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
    419         if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
    420         if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
    421         if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
    422         if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
    423         if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
    424         if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
    425         if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
    426 
    427         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
    428 
    429         /*
    430          * Use the second and fourth of the five sorted elements as pivots.
    431          * These values are inexpensive approximations of the first and
    432          * second terciles of the array. Note that pivot1 <= pivot2.
    433          *
    434          * The pivots are stored in local variables, and the first and
    435          * the last of the elements to be sorted are moved to the locations
    436          * formerly occupied by the pivots. When partitioning is complete,
    437          * the pivots are swapped back into their final positions, and
    438          * excluded from subsequent sorting.
    439          */
    440         long pivot1 = ae2; a[e2] = a[left];
    441         long pivot2 = ae4; a[e4] = a[right];
    442 
    443         // Pointers
    444         int less  = left  + 1; // The index of first element of center part
    445         int great = right - 1; // The index before first element of right part
    446 
    447         boolean pivotsDiffer = (pivot1 != pivot2);
    448 
    449         if (pivotsDiffer) {
    450             /*
    451              * Partitioning:
    452              *
    453              *   left part         center part                    right part
    454              * +------------------------------------------------------------+
    455              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
    456              * +------------------------------------------------------------+
    457              *              ^                          ^       ^
    458              *              |                          |       |
    459              *             less                        k     great
    460              *
    461              * Invariants:
    462              *
    463              *              all in (left, less)   < pivot1
    464              *    pivot1 <= all in [less, k)     <= pivot2
    465              *              all in (great, right) > pivot2
    466              *
    467              * Pointer k is the first index of ?-part
    468              */
    469             outer:
    470             for (int k = less; k <= great; k++) {
    471                 long ak = a[k];
    472                 if (ak < pivot1) { // Move a[k] to left part
    473                     if (k != less) {
    474                         a[k] = a[less];
    475                         a[less] = ak;
    476                     }
    477                     less++;
    478                 } else if (ak > pivot2) { // Move a[k] to right part
    479                     while (a[great] > pivot2) {
    480                         if (great-- == k) {
    481                             break outer;
    482                         }
    483                     }
    484                     if (a[great] < pivot1) {
    485                         a[k] = a[less];
    486                         a[less++] = a[great];
    487                         a[great--] = ak;
    488                     } else { // pivot1 <= a[great] <= pivot2
    489                         a[k] = a[great];
    490                         a[great--] = ak;
    491                     }
    492                 }
    493             }
    494         } else { // Pivots are equal
    495             /*
    496              * Partition degenerates to the traditional 3-way,
    497              * or "Dutch National Flag", partition:
    498              *
    499              *   left part   center part            right part
    500              * +----------------------------------------------+
    501              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
    502              * +----------------------------------------------+
    503              *              ^            ^       ^
    504              *              |            |       |
    505              *             less          k     great
    506              *
    507              * Invariants:
    508              *
    509              *   all in (left, less)   < pivot
    510              *   all in [less, k)     == pivot
    511              *   all in (great, right) > pivot
    512              *
    513              * Pointer k is the first index of ?-part
    514              */
    515             for (int k = less; k <= great; k++) {
    516                 long ak = a[k];
    517                 if (ak == pivot1) {
    518                     continue;
    519                 }
    520                 if (ak < pivot1) { // Move a[k] to left part
    521                     if (k != less) {
    522                         a[k] = a[less];
    523                         a[less] = ak;
    524                     }
    525                     less++;
    526                 } else { // (a[k] > pivot1) -  Move a[k] to right part
    527                     /*
    528                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
    529                      * that great will still be >= k when the following loop
    530                      * terminates, even though we don't test for it explicitly.
    531                      * In other words, a[e3] acts as a sentinel for great.
    532                      */
    533                     while (a[great] > pivot1) {
    534                         great--;
    535                     }
    536                     if (a[great] < pivot1) {
    537                         a[k] = a[less];
    538                         a[less++] = a[great];
    539                         a[great--] = ak;
    540                     } else { // a[great] == pivot1
    541                         a[k] = pivot1;
    542                         a[great--] = ak;
    543                     }
    544                 }
    545             }
    546         }
    547 
    548         // Swap pivots into their final positions
    549         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    550         a[right] = a[great + 1]; a[great + 1] = pivot2;
    551 
    552         // Sort left and right parts recursively, excluding known pivot values
    553         doSort(a, left,   less - 2);
    554         doSort(a, great + 2, right);
    555 
    556         /*
    557          * If pivot1 == pivot2, all elements from center
    558          * part are equal and, therefore, already sorted
    559          */
    560         if (!pivotsDiffer) {
    561             return;
    562         }
    563 
    564         /*
    565          * If center part is too large (comprises > 2/3 of the array),
    566          * swap internal pivot values to ends
    567          */
    568         if (less < e1 && great > e5) {
    569             while (a[less] == pivot1) {
    570                 less++;
    571             }
    572             while (a[great] == pivot2) {
    573                 great--;
    574             }
    575 
    576             /*
    577              * Partitioning:
    578              *
    579              *   left part       center part                   right part
    580              * +----------------------------------------------------------+
    581              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
    582              * +----------------------------------------------------------+
    583              *              ^                        ^       ^
    584              *              |                        |       |
    585              *             less                      k     great
    586              *
    587              * Invariants:
    588              *
    589              *              all in (*, less)  == pivot1
    590              *     pivot1 < all in [less, k)   < pivot2
    591              *              all in (great, *) == pivot2
    592              *
    593              * Pointer k is the first index of ?-part
    594              */
    595             outer:
    596             for (int k = less; k <= great; k++) {
    597                 long ak = a[k];
    598                 if (ak == pivot2) { // Move a[k] to right part
    599                     while (a[great] == pivot2) {
    600                         if (great-- == k) {
    601                             break outer;
    602                         }
    603                     }
    604                     if (a[great] == pivot1) {
    605                         a[k] = a[less];
    606                         a[less++] = pivot1;
    607                     } else { // pivot1 < a[great] < pivot2
    608                         a[k] = a[great];
    609                     }
    610                     a[great--] = pivot2;
    611                 } else if (ak == pivot1) { // Move a[k] to left part
    612                     a[k] = a[less];
    613                     a[less++] = pivot1;
    614                 }
    615             }
    616         }
    617 
    618         // Sort center part recursively, excluding known pivot values
    619         doSort(a, less, great);
    620     }
    621 
    622     /**
    623      * Sorts the specified array into ascending numerical order.
    624      *
    625      * @param a the array to be sorted
    626      */
    627     public static void sort(short[] a) {
    628         doSort(a, 0, a.length - 1);
    629     }
    630 
    631     /**
    632      * Sorts the specified range of the array into ascending order. The range
    633      * to be sorted extends from the index {@code fromIndex}, inclusive, to
    634      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
    635      * the range to be sorted is empty (and the call is a no-op).
    636      *
    637      * @param a the array to be sorted
    638      * @param fromIndex the index of the first element, inclusive, to be sorted
    639      * @param toIndex the index of the last element, exclusive, to be sorted
    640      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
    641      * @throws ArrayIndexOutOfBoundsException
    642      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
    643      */
    644     public static void sort(short[] a, int fromIndex, int toIndex) {
    645         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
    646         doSort(a, fromIndex, toIndex - 1);
    647     }
    648 
    649     /** The number of distinct short values. */
    650     private static final int NUM_SHORT_VALUES = 1 << 16;
    651 
    652     /**
    653      * Sorts the specified range of the array into ascending order. This
    654      * method differs from the public {@code sort} method in that the
    655      * {@code right} index is inclusive, and it does no range checking on
    656      * {@code left} or {@code right}.
    657      *
    658      * @param a the array to be sorted
    659      * @param left the index of the first element, inclusive, to be sorted
    660      * @param right the index of the last element, inclusive, to be sorted
    661      */
    662     private static void doSort(short[] a, int left, int right) {
    663         // Use insertion sort on tiny arrays
    664         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
    665             for (int i = left + 1; i <= right; i++) {
    666                 short ai = a[i];
    667                 int j;
    668                 for (j = i - 1; j >= left && ai < a[j]; j--) {
    669                     a[j + 1] = a[j];
    670                 }
    671                 a[j + 1] = ai;
    672             }
    673         } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
    674             // Use counting sort on huge arrays
    675             int[] count = new int[NUM_SHORT_VALUES];
    676 
    677             for (int i = left; i <= right; i++) {
    678                 count[a[i] - Short.MIN_VALUE]++;
    679             }
    680             for (int i = 0, k = left; i < count.length && k <= right; i++) {
    681                 short value = (short) (i + Short.MIN_VALUE);
    682 
    683                 for (int s = count[i]; s > 0; s--) {
    684                     a[k++] = value;
    685                }
    686             }
    687         } else { // Use Dual-Pivot Quicksort on large arrays
    688             dualPivotQuicksort(a, left, right);
    689         }
    690     }
    691 
    692     /**
    693      * Sorts the specified range of the array into ascending order by the
    694      * Dual-Pivot Quicksort algorithm.
    695      *
    696      * @param a the array to be sorted
    697      * @param left the index of the first element, inclusive, to be sorted
    698      * @param right the index of the last element, inclusive, to be sorted
    699      */
    700     private static void dualPivotQuicksort(short[] a, int left, int right) {
    701         // Compute indices of five evenly spaced elements
    702         int sixth = (right - left + 1) / 6;
    703         int e1 = left  + sixth;
    704         int e5 = right - sixth;
    705         int e3 = (left + right) >>> 1; // The midpoint
    706         int e4 = e3 + sixth;
    707         int e2 = e3 - sixth;
    708 
    709         // Sort these elements using a 5-element sorting network
    710         short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
    711 
    712         if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
    713         if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
    714         if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
    715         if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
    716         if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
    717         if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
    718         if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
    719         if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
    720         if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
    721 
    722         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
    723 
    724         /*
    725          * Use the second and fourth of the five sorted elements as pivots.
    726          * These values are inexpensive approximations of the first and
    727          * second terciles of the array. Note that pivot1 <= pivot2.
    728          *
    729          * The pivots are stored in local variables, and the first and
    730          * the last of the elements to be sorted are moved to the locations
    731          * formerly occupied by the pivots. When partitioning is complete,
    732          * the pivots are swapped back into their final positions, and
    733          * excluded from subsequent sorting.
    734          */
    735         short pivot1 = ae2; a[e2] = a[left];
    736         short pivot2 = ae4; a[e4] = a[right];
    737 
    738         // Pointers
    739         int less  = left  + 1; // The index of first element of center part
    740         int great = right - 1; // The index before first element of right part
    741 
    742         boolean pivotsDiffer = (pivot1 != pivot2);
    743 
    744         if (pivotsDiffer) {
    745             /*
    746              * Partitioning:
    747              *
    748              *   left part         center part                    right part
    749              * +------------------------------------------------------------+
    750              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
    751              * +------------------------------------------------------------+
    752              *              ^                          ^       ^
    753              *              |                          |       |
    754              *             less                        k     great
    755              *
    756              * Invariants:
    757              *
    758              *              all in (left, less)   < pivot1
    759              *    pivot1 <= all in [less, k)     <= pivot2
    760              *              all in (great, right) > pivot2
    761              *
    762              * Pointer k is the first index of ?-part
    763              */
    764             outer:
    765             for (int k = less; k <= great; k++) {
    766                 short ak = a[k];
    767                 if (ak < pivot1) { // Move a[k] to left part
    768                     if (k != less) {
    769                         a[k] = a[less];
    770                         a[less] = ak;
    771                     }
    772                     less++;
    773                 } else if (ak > pivot2) { // Move a[k] to right part
    774                     while (a[great] > pivot2) {
    775                         if (great-- == k) {
    776                             break outer;
    777                         }
    778                     }
    779                     if (a[great] < pivot1) {
    780                         a[k] = a[less];
    781                         a[less++] = a[great];
    782                         a[great--] = ak;
    783                     } else { // pivot1 <= a[great] <= pivot2
    784                         a[k] = a[great];
    785                         a[great--] = ak;
    786                     }
    787                 }
    788             }
    789         } else { // Pivots are equal
    790             /*
    791              * Partition degenerates to the traditional 3-way,
    792              * or "Dutch National Flag", partition:
    793              *
    794              *   left part   center part            right part
    795              * +----------------------------------------------+
    796              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
    797              * +----------------------------------------------+
    798              *              ^            ^       ^
    799              *              |            |       |
    800              *             less          k     great
    801              *
    802              * Invariants:
    803              *
    804              *   all in (left, less)   < pivot
    805              *   all in [less, k)     == pivot
    806              *   all in (great, right) > pivot
    807              *
    808              * Pointer k is the first index of ?-part
    809              */
    810             for (int k = less; k <= great; k++) {
    811                 short ak = a[k];
    812                 if (ak == pivot1) {
    813                     continue;
    814                 }
    815                 if (ak < pivot1) { // Move a[k] to left part
    816                     if (k != less) {
    817                         a[k] = a[less];
    818                         a[less] = ak;
    819                     }
    820                     less++;
    821                 } else { // (a[k] > pivot1) -  Move a[k] to right part
    822                     /*
    823                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
    824                      * that great will still be >= k when the following loop
    825                      * terminates, even though we don't test for it explicitly.
    826                      * In other words, a[e3] acts as a sentinel for great.
    827                      */
    828                     while (a[great] > pivot1) {
    829                         great--;
    830                     }
    831                     if (a[great] < pivot1) {
    832                         a[k] = a[less];
    833                         a[less++] = a[great];
    834                         a[great--] = ak;
    835                     } else { // a[great] == pivot1
    836                         a[k] = pivot1;
    837                         a[great--] = ak;
    838                     }
    839                 }
    840             }
    841         }
    842 
    843         // Swap pivots into their final positions
    844         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
    845         a[right] = a[great + 1]; a[great + 1] = pivot2;
    846 
    847         // Sort left and right parts recursively, excluding known pivot values
    848         doSort(a, left,   less - 2);
    849         doSort(a, great + 2, right);
    850 
    851         /*
    852          * If pivot1 == pivot2, all elements from center
    853          * part are equal and, therefore, already sorted
    854          */
    855         if (!pivotsDiffer) {
    856             return;
    857         }
    858 
    859         /*
    860          * If center part is too large (comprises > 2/3 of the array),
    861          * swap internal pivot values to ends
    862          */
    863         if (less < e1 && great > e5) {
    864             while (a[less] == pivot1) {
    865                 less++;
    866             }
    867             while (a[great] == pivot2) {
    868                 great--;
    869             }
    870 
    871             /*
    872              * Partitioning:
    873              *
    874              *   left part       center part                   right part
    875              * +----------------------------------------------------------+
    876              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
    877              * +----------------------------------------------------------+
    878              *              ^                        ^       ^
    879              *              |                        |       |
    880              *             less                      k     great
    881              *
    882              * Invariants:
    883              *
    884              *              all in (*, less)  == pivot1
    885              *     pivot1 < all in [less, k)   < pivot2
    886              *              all in (great, *) == pivot2
    887              *
    888              * Pointer k is the first index of ?-part
    889              */
    890             outer:
    891             for (int k = less; k <= great; k++) {
    892                 short ak = a[k];
    893                 if (ak == pivot2) { // Move a[k] to right part
    894                     while (a[great] == pivot2) {
    895                         if (great-- == k) {
    896                             break outer;
    897                         }
    898                     }
    899                     if (a[great] == pivot1) {
    900                         a[k] = a[less];
    901                         a[less++] = pivot1;
    902                     } else { // pivot1 < a[great] < pivot2
    903                         a[k] = a[great];
    904                     }
    905                     a[great--] = pivot2;
    906                 } else if (ak == pivot1) { // Move a[k] to left part
    907                     a[k] = a[less];
    908                     a[less++] = pivot1;
    909                 }
    910             }
    911         }
    912 
    913         // Sort center part recursively, excluding known pivot values
    914         doSort(a, less, great);
    915     }
    916 
    917     /**
    918      * Sorts the specified array into ascending numerical order.
    919      *
    920      * @param a the array to be sorted
    921      */
    922     public static void sort(char[] a) {
    923         doSort(a, 0, a.length - 1);
    924     }
    925 
    926     /**
    927      * Sorts the specified range of the array into ascending order. The range
    928      * to be sorted extends from the index {@code fromIndex}, inclusive, to
    929      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
    930      * the range to be sorted is empty (and the call is a no-op).
    931      *
    932      * @param a the array to be sorted
    933      * @param fromIndex the index of the first element, inclusive, to be sorted
    934      * @param toIndex the index of the last element, exclusive, to be sorted
    935      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
    936      * @throws ArrayIndexOutOfBoundsException
    937      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
    938      */
    939     public static void sort(char[] a, int fromIndex, int toIndex) {
    940         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
    941         doSort(a, fromIndex, toIndex - 1);
    942     }
    943 
    944     /** The number of distinct char values. */
    945     private static final int NUM_CHAR_VALUES = 1 << 16;
    946 
    947     /**
    948      * Sorts the specified range of the array into ascending order. This
    949      * method differs from the public {@code sort} method in that the
    950      * {@code right} index is inclusive, and it does no range checking on
    951      * {@code left} or {@code right}.
    952      *
    953      * @param a the array to be sorted
    954      * @param left the index of the first element, inclusive, to be sorted
    955      * @param right the index of the last element, inclusive, to be sorted
    956      */
    957     private static void doSort(char[] a, int left, int right) {
    958         // Use insertion sort on tiny arrays
    959         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
    960             for (int i = left + 1; i <= right; i++) {
    961                 char ai = a[i];
    962                 int j;
    963                 for (j = i - 1; j >= left && ai < a[j]; j--) {
    964                     a[j + 1] = a[j];
    965                 }
    966                 a[j + 1] = ai;
    967             }
    968         } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
    969             // Use counting sort on huge arrays
    970             int[] count = new int[NUM_CHAR_VALUES];
    971 
    972             for (int i = left; i <= right; i++) {
    973                 count[a[i]]++;
    974             }
    975             for (int i = 0, k = left; i < count.length && k <= right; i++) {
    976                 for (int s = count[i]; s > 0; s--) {
    977                     a[k++] = (char) i;
    978                }
    979             }
    980         } else { // Use Dual-Pivot Quicksort on large arrays
    981             dualPivotQuicksort(a, left, right);
    982         }
    983     }
    984 
    985     /**
    986      * Sorts the specified range of the array into ascending order by the
    987      * Dual-Pivot Quicksort algorithm.
    988      *
    989      * @param a the array to be sorted
    990      * @param left the index of the first element, inclusive, to be sorted
    991      * @param right the index of the last element, inclusive, to be sorted
    992      */
    993     private static void dualPivotQuicksort(char[] a, int left, int right) {
    994         // Compute indices of five evenly spaced elements
    995         int sixth = (right - left + 1) / 6;
    996         int e1 = left  + sixth;
    997         int e5 = right - sixth;
    998         int e3 = (left + right) >>> 1; // The midpoint
    999         int e4 = e3 + sixth;
   1000         int e2 = e3 - sixth;
   1001 
   1002         // Sort these elements using a 5-element sorting network
   1003         char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
   1004 
   1005         if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
   1006         if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
   1007         if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
   1008         if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
   1009         if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
   1010         if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
   1011         if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
   1012         if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
   1013         if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
   1014 
   1015         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
   1016 
   1017         /*
   1018          * Use the second and fourth of the five sorted elements as pivots.
   1019          * These values are inexpensive approximations of the first and
   1020          * second terciles of the array. Note that pivot1 <= pivot2.
   1021          *
   1022          * The pivots are stored in local variables, and the first and
   1023          * the last of the elements to be sorted are moved to the locations
   1024          * formerly occupied by the pivots. When partitioning is complete,
   1025          * the pivots are swapped back into their final positions, and
   1026          * excluded from subsequent sorting.
   1027          */
   1028         char pivot1 = ae2; a[e2] = a[left];
   1029         char pivot2 = ae4; a[e4] = a[right];
   1030 
   1031         // Pointers
   1032         int less  = left  + 1; // The index of first element of center part
   1033         int great = right - 1; // The index before first element of right part
   1034 
   1035         boolean pivotsDiffer = (pivot1 != pivot2);
   1036 
   1037         if (pivotsDiffer) {
   1038             /*
   1039              * Partitioning:
   1040              *
   1041              *   left part         center part                    right part
   1042              * +------------------------------------------------------------+
   1043              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
   1044              * +------------------------------------------------------------+
   1045              *              ^                          ^       ^
   1046              *              |                          |       |
   1047              *             less                        k     great
   1048              *
   1049              * Invariants:
   1050              *
   1051              *              all in (left, less)   < pivot1
   1052              *    pivot1 <= all in [less, k)     <= pivot2
   1053              *              all in (great, right) > pivot2
   1054              *
   1055              * Pointer k is the first index of ?-part
   1056              */
   1057             outer:
   1058             for (int k = less; k <= great; k++) {
   1059                 char ak = a[k];
   1060                 if (ak < pivot1) { // Move a[k] to left part
   1061                     if (k != less) {
   1062                         a[k] = a[less];
   1063                         a[less] = ak;
   1064                     }
   1065                     less++;
   1066                 } else if (ak > pivot2) { // Move a[k] to right part
   1067                     while (a[great] > pivot2) {
   1068                         if (great-- == k) {
   1069                             break outer;
   1070                         }
   1071                     }
   1072                     if (a[great] < pivot1) {
   1073                         a[k] = a[less];
   1074                         a[less++] = a[great];
   1075                         a[great--] = ak;
   1076                     } else { // pivot1 <= a[great] <= pivot2
   1077                         a[k] = a[great];
   1078                         a[great--] = ak;
   1079                     }
   1080                 }
   1081             }
   1082         } else { // Pivots are equal
   1083             /*
   1084              * Partition degenerates to the traditional 3-way,
   1085              * or "Dutch National Flag", partition:
   1086              *
   1087              *   left part   center part            right part
   1088              * +----------------------------------------------+
   1089              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
   1090              * +----------------------------------------------+
   1091              *              ^            ^       ^
   1092              *              |            |       |
   1093              *             less          k     great
   1094              *
   1095              * Invariants:
   1096              *
   1097              *   all in (left, less)   < pivot
   1098              *   all in [less, k)     == pivot
   1099              *   all in (great, right) > pivot
   1100              *
   1101              * Pointer k is the first index of ?-part
   1102              */
   1103             for (int k = less; k <= great; k++) {
   1104                 char ak = a[k];
   1105                 if (ak == pivot1) {
   1106                     continue;
   1107                 }
   1108                 if (ak < pivot1) { // Move a[k] to left part
   1109                     if (k != less) {
   1110                         a[k] = a[less];
   1111                         a[less] = ak;
   1112                     }
   1113                     less++;
   1114                 } else { // (a[k] > pivot1) -  Move a[k] to right part
   1115                     /*
   1116                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
   1117                      * that great will still be >= k when the following loop
   1118                      * terminates, even though we don't test for it explicitly.
   1119                      * In other words, a[e3] acts as a sentinel for great.
   1120                      */
   1121                     while (a[great] > pivot1) {
   1122                         great--;
   1123                     }
   1124                     if (a[great] < pivot1) {
   1125                         a[k] = a[less];
   1126                         a[less++] = a[great];
   1127                         a[great--] = ak;
   1128                     } else { // a[great] == pivot1
   1129                         a[k] = pivot1;
   1130                         a[great--] = ak;
   1131                     }
   1132                 }
   1133             }
   1134         }
   1135 
   1136         // Swap pivots into their final positions
   1137         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
   1138         a[right] = a[great + 1]; a[great + 1] = pivot2;
   1139 
   1140         // Sort left and right parts recursively, excluding known pivot values
   1141         doSort(a, left,   less - 2);
   1142         doSort(a, great + 2, right);
   1143 
   1144         /*
   1145          * If pivot1 == pivot2, all elements from center
   1146          * part are equal and, therefore, already sorted
   1147          */
   1148         if (!pivotsDiffer) {
   1149             return;
   1150         }
   1151 
   1152         /*
   1153          * If center part is too large (comprises > 2/3 of the array),
   1154          * swap internal pivot values to ends
   1155          */
   1156         if (less < e1 && great > e5) {
   1157             while (a[less] == pivot1) {
   1158                 less++;
   1159             }
   1160             while (a[great] == pivot2) {
   1161                 great--;
   1162             }
   1163 
   1164             /*
   1165              * Partitioning:
   1166              *
   1167              *   left part       center part                   right part
   1168              * +----------------------------------------------------------+
   1169              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
   1170              * +----------------------------------------------------------+
   1171              *              ^                        ^       ^
   1172              *              |                        |       |
   1173              *             less                      k     great
   1174              *
   1175              * Invariants:
   1176              *
   1177              *              all in (*, less)  == pivot1
   1178              *     pivot1 < all in [less, k)   < pivot2
   1179              *              all in (great, *) == pivot2
   1180              *
   1181              * Pointer k is the first index of ?-part
   1182              */
   1183             outer:
   1184             for (int k = less; k <= great; k++) {
   1185                 char ak = a[k];
   1186                 if (ak == pivot2) { // Move a[k] to right part
   1187                     while (a[great] == pivot2) {
   1188                         if (great-- == k) {
   1189                             break outer;
   1190                         }
   1191                     }
   1192                     if (a[great] == pivot1) {
   1193                         a[k] = a[less];
   1194                         a[less++] = pivot1;
   1195                     } else { // pivot1 < a[great] < pivot2
   1196                         a[k] = a[great];
   1197                     }
   1198                     a[great--] = pivot2;
   1199                 } else if (ak == pivot1) { // Move a[k] to left part
   1200                     a[k] = a[less];
   1201                     a[less++] = pivot1;
   1202                 }
   1203             }
   1204         }
   1205 
   1206         // Sort center part recursively, excluding known pivot values
   1207         doSort(a, less, great);
   1208     }
   1209 
   1210     /**
   1211      * Sorts the specified array into ascending numerical order.
   1212      *
   1213      * @param a the array to be sorted
   1214      */
   1215     public static void sort(byte[] a) {
   1216         doSort(a, 0, a.length - 1);
   1217     }
   1218 
   1219     /**
   1220      * Sorts the specified range of the array into ascending order. The range
   1221      * to be sorted extends from the index {@code fromIndex}, inclusive, to
   1222      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
   1223      * the range to be sorted is empty (and the call is a no-op).
   1224      *
   1225      * @param a the array to be sorted
   1226      * @param fromIndex the index of the first element, inclusive, to be sorted
   1227      * @param toIndex the index of the last element, exclusive, to be sorted
   1228      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
   1229      * @throws ArrayIndexOutOfBoundsException
   1230      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
   1231      */
   1232     public static void sort(byte[] a, int fromIndex, int toIndex) {
   1233         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
   1234         doSort(a, fromIndex, toIndex - 1);
   1235     }
   1236 
   1237     /** The number of distinct byte values. */
   1238     private static final int NUM_BYTE_VALUES = 1 << 8;
   1239 
   1240     /**
   1241      * Sorts the specified range of the array into ascending order. This
   1242      * method differs from the public {@code sort} method in that the
   1243      * {@code right} index is inclusive, and it does no range checking on
   1244      * {@code left} or {@code right}.
   1245      *
   1246      * @param a the array to be sorted
   1247      * @param left the index of the first element, inclusive, to be sorted
   1248      * @param right the index of the last element, inclusive, to be sorted
   1249      */
   1250     private static void doSort(byte[] a, int left, int right) {
   1251         // Use insertion sort on tiny arrays
   1252         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
   1253             for (int i = left + 1; i <= right; i++) {
   1254                 byte ai = a[i];
   1255                 int j;
   1256                 for (j = i - 1; j >= left && ai < a[j]; j--) {
   1257                     a[j + 1] = a[j];
   1258                 }
   1259                 a[j + 1] = ai;
   1260             }
   1261         } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
   1262             // Use counting sort on huge arrays
   1263             int[] count = new int[NUM_BYTE_VALUES];
   1264 
   1265             for (int i = left; i <= right; i++) {
   1266                 count[a[i] - Byte.MIN_VALUE]++;
   1267             }
   1268             for (int i = 0, k = left; i < count.length && k <= right; i++) {
   1269                 byte value = (byte) (i + Byte.MIN_VALUE);
   1270 
   1271                 for (int s = count[i]; s > 0; s--) {
   1272                     a[k++] = value;
   1273                }
   1274             }
   1275         } else { // Use Dual-Pivot Quicksort on large arrays
   1276             dualPivotQuicksort(a, left, right);
   1277         }
   1278     }
   1279 
   1280     /**
   1281      * Sorts the specified range of the array into ascending order by the
   1282      * Dual-Pivot Quicksort algorithm.
   1283      *
   1284      * @param a the array to be sorted
   1285      * @param left the index of the first element, inclusive, to be sorted
   1286      * @param right the index of the last element, inclusive, to be sorted
   1287      */
   1288     private static void dualPivotQuicksort(byte[] a, int left, int right) {
   1289         // Compute indices of five evenly spaced elements
   1290         int sixth = (right - left + 1) / 6;
   1291         int e1 = left  + sixth;
   1292         int e5 = right - sixth;
   1293         int e3 = (left + right) >>> 1; // The midpoint
   1294         int e4 = e3 + sixth;
   1295         int e2 = e3 - sixth;
   1296 
   1297         // Sort these elements using a 5-element sorting network
   1298         byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
   1299 
   1300         if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
   1301         if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
   1302         if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
   1303         if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
   1304         if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
   1305         if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
   1306         if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
   1307         if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
   1308         if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
   1309 
   1310         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
   1311 
   1312         /*
   1313          * Use the second and fourth of the five sorted elements as pivots.
   1314          * These values are inexpensive approximations of the first and
   1315          * second terciles of the array. Note that pivot1 <= pivot2.
   1316          *
   1317          * The pivots are stored in local variables, and the first and
   1318          * the last of the elements to be sorted are moved to the locations
   1319          * formerly occupied by the pivots. When partitioning is complete,
   1320          * the pivots are swapped back into their final positions, and
   1321          * excluded from subsequent sorting.
   1322          */
   1323         byte pivot1 = ae2; a[e2] = a[left];
   1324         byte pivot2 = ae4; a[e4] = a[right];
   1325 
   1326         // Pointers
   1327         int less  = left  + 1; // The index of first element of center part
   1328         int great = right - 1; // The index before first element of right part
   1329 
   1330         boolean pivotsDiffer = (pivot1 != pivot2);
   1331 
   1332         if (pivotsDiffer) {
   1333             /*
   1334              * Partitioning:
   1335              *
   1336              *   left part         center part                    right part
   1337              * +------------------------------------------------------------+
   1338              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
   1339              * +------------------------------------------------------------+
   1340              *              ^                          ^       ^
   1341              *              |                          |       |
   1342              *             less                        k     great
   1343              *
   1344              * Invariants:
   1345              *
   1346              *              all in (left, less)   < pivot1
   1347              *    pivot1 <= all in [less, k)     <= pivot2
   1348              *              all in (great, right) > pivot2
   1349              *
   1350              * Pointer k is the first index of ?-part
   1351              */
   1352             outer:
   1353             for (int k = less; k <= great; k++) {
   1354                 byte ak = a[k];
   1355                 if (ak < pivot1) { // Move a[k] to left part
   1356                     if (k != less) {
   1357                         a[k] = a[less];
   1358                         a[less] = ak;
   1359                     }
   1360                     less++;
   1361                 } else if (ak > pivot2) { // Move a[k] to right part
   1362                     while (a[great] > pivot2) {
   1363                         if (great-- == k) {
   1364                             break outer;
   1365                         }
   1366                     }
   1367                     if (a[great] < pivot1) {
   1368                         a[k] = a[less];
   1369                         a[less++] = a[great];
   1370                         a[great--] = ak;
   1371                     } else { // pivot1 <= a[great] <= pivot2
   1372                         a[k] = a[great];
   1373                         a[great--] = ak;
   1374                     }
   1375                 }
   1376             }
   1377         } else { // Pivots are equal
   1378             /*
   1379              * Partition degenerates to the traditional 3-way,
   1380              * or "Dutch National Flag", partition:
   1381              *
   1382              *   left part   center part            right part
   1383              * +----------------------------------------------+
   1384              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
   1385              * +----------------------------------------------+
   1386              *              ^            ^       ^
   1387              *              |            |       |
   1388              *             less          k     great
   1389              *
   1390              * Invariants:
   1391              *
   1392              *   all in (left, less)   < pivot
   1393              *   all in [less, k)     == pivot
   1394              *   all in (great, right) > pivot
   1395              *
   1396              * Pointer k is the first index of ?-part
   1397              */
   1398             for (int k = less; k <= great; k++) {
   1399                 byte ak = a[k];
   1400                 if (ak == pivot1) {
   1401                     continue;
   1402                 }
   1403                 if (ak < pivot1) { // Move a[k] to left part
   1404                     if (k != less) {
   1405                         a[k] = a[less];
   1406                         a[less] = ak;
   1407                     }
   1408                     less++;
   1409                 } else { // (a[k] > pivot1) -  Move a[k] to right part
   1410                     /*
   1411                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
   1412                      * that great will still be >= k when the following loop
   1413                      * terminates, even though we don't test for it explicitly.
   1414                      * In other words, a[e3] acts as a sentinel for great.
   1415                      */
   1416                     while (a[great] > pivot1) {
   1417                         great--;
   1418                     }
   1419                     if (a[great] < pivot1) {
   1420                         a[k] = a[less];
   1421                         a[less++] = a[great];
   1422                         a[great--] = ak;
   1423                     } else { // a[great] == pivot1
   1424                         a[k] = pivot1;
   1425                         a[great--] = ak;
   1426                     }
   1427                 }
   1428             }
   1429         }
   1430 
   1431         // Swap pivots into their final positions
   1432         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
   1433         a[right] = a[great + 1]; a[great + 1] = pivot2;
   1434 
   1435         // Sort left and right parts recursively, excluding known pivot values
   1436         doSort(a, left,   less - 2);
   1437         doSort(a, great + 2, right);
   1438 
   1439         /*
   1440          * If pivot1 == pivot2, all elements from center
   1441          * part are equal and, therefore, already sorted
   1442          */
   1443         if (!pivotsDiffer) {
   1444             return;
   1445         }
   1446 
   1447         /*
   1448          * If center part is too large (comprises > 2/3 of the array),
   1449          * swap internal pivot values to ends
   1450          */
   1451         if (less < e1 && great > e5) {
   1452             while (a[less] == pivot1) {
   1453                 less++;
   1454             }
   1455             while (a[great] == pivot2) {
   1456                 great--;
   1457             }
   1458 
   1459             /*
   1460              * Partitioning:
   1461              *
   1462              *   left part       center part                   right part
   1463              * +----------------------------------------------------------+
   1464              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
   1465              * +----------------------------------------------------------+
   1466              *              ^                        ^       ^
   1467              *              |                        |       |
   1468              *             less                      k     great
   1469              *
   1470              * Invariants:
   1471              *
   1472              *              all in (*, less)  == pivot1
   1473              *     pivot1 < all in [less, k)   < pivot2
   1474              *              all in (great, *) == pivot2
   1475              *
   1476              * Pointer k is the first index of ?-part
   1477              */
   1478             outer:
   1479             for (int k = less; k <= great; k++) {
   1480                 byte ak = a[k];
   1481                 if (ak == pivot2) { // Move a[k] to right part
   1482                     while (a[great] == pivot2) {
   1483                         if (great-- == k) {
   1484                             break outer;
   1485                         }
   1486                     }
   1487                     if (a[great] == pivot1) {
   1488                         a[k] = a[less];
   1489                         a[less++] = pivot1;
   1490                     } else { // pivot1 < a[great] < pivot2
   1491                         a[k] = a[great];
   1492                     }
   1493                     a[great--] = pivot2;
   1494                 } else if (ak == pivot1) { // Move a[k] to left part
   1495                     a[k] = a[less];
   1496                     a[less++] = pivot1;
   1497                 }
   1498             }
   1499         }
   1500 
   1501         // Sort center part recursively, excluding known pivot values
   1502         doSort(a, less, great);
   1503     }
   1504 
   1505     /**
   1506      * Sorts the specified array into ascending numerical order.
   1507      *
   1508      * <p>The {@code <} relation does not provide a total order on all float
   1509      * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
   1510      * value compares neither less than, greater than, nor equal to any value,
   1511      * even itself. This method uses the total order imposed by the method
   1512      * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
   1513      * {@code 0.0f} and {@code Float.NaN} is considered greater than any
   1514      * other value and all {@code Float.NaN} values are considered equal.
   1515      *
   1516      * @param a the array to be sorted
   1517      */
   1518     public static void sort(float[] a) {
   1519         sortNegZeroAndNaN(a, 0, a.length - 1);
   1520     }
   1521 
   1522     /**
   1523      * Sorts the specified range of the array into ascending order. The range
   1524      * to be sorted extends from the index {@code fromIndex}, inclusive, to
   1525      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
   1526      * the range to be sorted is empty  and the call is a no-op).
   1527      *
   1528      * <p>The {@code <} relation does not provide a total order on all float
   1529      * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
   1530      * value compares neither less than, greater than, nor equal to any value,
   1531      * even itself. This method uses the total order imposed by the method
   1532      * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
   1533      * {@code 0.0f} and {@code Float.NaN} is considered greater than any
   1534      * other value and all {@code Float.NaN} values are considered equal.
   1535      *
   1536      * @param a the array to be sorted
   1537      * @param fromIndex the index of the first element, inclusive, to be sorted
   1538      * @param toIndex the index of the last element, exclusive, to be sorted
   1539      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
   1540      * @throws ArrayIndexOutOfBoundsException
   1541      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
   1542      */
   1543     public static void sort(float[] a, int fromIndex, int toIndex) {
   1544         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
   1545         sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
   1546     }
   1547 
   1548     /**
   1549      * Sorts the specified range of the array into ascending order. The
   1550      * sort is done in three phases to avoid expensive comparisons in the
   1551      * inner loop. The comparisons would be expensive due to anomalies
   1552      * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
   1553      *
   1554      * @param a the array to be sorted
   1555      * @param left the index of the first element, inclusive, to be sorted
   1556      * @param right the index of the last element, inclusive, to be sorted
   1557      */
   1558     private static void sortNegZeroAndNaN(float[] a, int left, int right) {
   1559         /*
   1560          * Phase 1: Count negative zeros and move NaNs to end of array
   1561          */
   1562         final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
   1563         int numNegativeZeros = 0;
   1564         int n = right;
   1565 
   1566         for (int k = left; k <= n; k++) {
   1567             float ak = a[k];
   1568             if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToRawIntBits(ak)) {
   1569                 a[k] = 0.0f;
   1570                 numNegativeZeros++;
   1571             } else if (ak != ak) { // i.e., ak is NaN
   1572                 a[k--] = a[n];
   1573                 a[n--] = Float.NaN;
   1574             }
   1575         }
   1576 
   1577         /*
   1578          * Phase 2: Sort everything except NaNs (which are already in place)
   1579          */
   1580         doSort(a, left, n);
   1581 
   1582         /*
   1583          * Phase 3: Turn positive zeros back into negative zeros as appropriate
   1584          */
   1585         if (numNegativeZeros == 0) {
   1586             return;
   1587         }
   1588 
   1589         // Find first zero element
   1590         int zeroIndex = findAnyZero(a, left, n);
   1591 
   1592         for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
   1593             zeroIndex = i;
   1594         }
   1595 
   1596         // Turn the right number of positive zeros back into negative zeros
   1597         for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
   1598             a[i] = -0.0f;
   1599         }
   1600     }
   1601 
   1602     /**
   1603      * Returns the index of some zero element in the specified range via
   1604      * binary search. The range is assumed to be sorted, and must contain
   1605      * at least one zero.
   1606      *
   1607      * @param a the array to be searched
   1608      * @param low the index of the first element, inclusive, to be searched
   1609      * @param high the index of the last element, inclusive, to be searched
   1610      */
   1611     private static int findAnyZero(float[] a, int low, int high) {
   1612         while (true) {
   1613             int middle = (low + high) >>> 1;
   1614             float middleValue = a[middle];
   1615 
   1616             if (middleValue < 0.0f) {
   1617                 low = middle + 1;
   1618             } else if (middleValue > 0.0f) {
   1619                 high = middle - 1;
   1620             } else { // middleValue == 0.0f
   1621                 return middle;
   1622             }
   1623         }
   1624     }
   1625 
   1626     /**
   1627      * Sorts the specified range of the array into ascending order. This
   1628      * method differs from the public {@code sort} method in three ways:
   1629      * {@code right} index is inclusive, it does no range checking on
   1630      * {@code left} or {@code right}, and it does not handle negative
   1631      * zeros or NaNs in the array.
   1632      *
   1633      * @param a the array to be sorted, which must not contain -0.0f or NaN
   1634      * @param left the index of the first element, inclusive, to be sorted
   1635      * @param right the index of the last element, inclusive, to be sorted
   1636      */
   1637     private static void doSort(float[] a, int left, int right) {
   1638         // Use insertion sort on tiny arrays
   1639         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
   1640             for (int i = left + 1; i <= right; i++) {
   1641                 float ai = a[i];
   1642                 int j;
   1643                 for (j = i - 1; j >= left && ai < a[j]; j--) {
   1644                     a[j + 1] = a[j];
   1645                 }
   1646                 a[j + 1] = ai;
   1647             }
   1648         } else { // Use Dual-Pivot Quicksort on large arrays
   1649             dualPivotQuicksort(a, left, right);
   1650         }
   1651     }
   1652 
   1653     /**
   1654      * Sorts the specified range of the array into ascending order by the
   1655      * Dual-Pivot Quicksort algorithm.
   1656      *
   1657      * @param a the array to be sorted
   1658      * @param left the index of the first element, inclusive, to be sorted
   1659      * @param right the index of the last element, inclusive, to be sorted
   1660      */
   1661     private static void dualPivotQuicksort(float[] a, int left, int right) {
   1662         // Compute indices of five evenly spaced elements
   1663         int sixth = (right - left + 1) / 6;
   1664         int e1 = left  + sixth;
   1665         int e5 = right - sixth;
   1666         int e3 = (left + right) >>> 1; // The midpoint
   1667         int e4 = e3 + sixth;
   1668         int e2 = e3 - sixth;
   1669 
   1670         // Sort these elements using a 5-element sorting network
   1671         float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
   1672 
   1673         if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
   1674         if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
   1675         if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
   1676         if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
   1677         if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
   1678         if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
   1679         if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
   1680         if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
   1681         if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
   1682 
   1683         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
   1684 
   1685         /*
   1686          * Use the second and fourth of the five sorted elements as pivots.
   1687          * These values are inexpensive approximations of the first and
   1688          * second terciles of the array. Note that pivot1 <= pivot2.
   1689          *
   1690          * The pivots are stored in local variables, and the first and
   1691          * the last of the elements to be sorted are moved to the locations
   1692          * formerly occupied by the pivots. When partitioning is complete,
   1693          * the pivots are swapped back into their final positions, and
   1694          * excluded from subsequent sorting.
   1695          */
   1696         float pivot1 = ae2; a[e2] = a[left];
   1697         float pivot2 = ae4; a[e4] = a[right];
   1698 
   1699         // Pointers
   1700         int less  = left  + 1; // The index of first element of center part
   1701         int great = right - 1; // The index before first element of right part
   1702 
   1703         boolean pivotsDiffer = (pivot1 != pivot2);
   1704 
   1705         if (pivotsDiffer) {
   1706             /*
   1707              * Partitioning:
   1708              *
   1709              *   left part         center part                    right part
   1710              * +------------------------------------------------------------+
   1711              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
   1712              * +------------------------------------------------------------+
   1713              *              ^                          ^       ^
   1714              *              |                          |       |
   1715              *             less                        k     great
   1716              *
   1717              * Invariants:
   1718              *
   1719              *              all in (left, less)   < pivot1
   1720              *    pivot1 <= all in [less, k)     <= pivot2
   1721              *              all in (great, right) > pivot2
   1722              *
   1723              * Pointer k is the first index of ?-part
   1724              */
   1725             outer:
   1726             for (int k = less; k <= great; k++) {
   1727                 float ak = a[k];
   1728                 if (ak < pivot1) { // Move a[k] to left part
   1729                     if (k != less) {
   1730                         a[k] = a[less];
   1731                         a[less] = ak;
   1732                     }
   1733                     less++;
   1734                 } else if (ak > pivot2) { // Move a[k] to right part
   1735                     while (a[great] > pivot2) {
   1736                         if (great-- == k) {
   1737                             break outer;
   1738                         }
   1739                     }
   1740                     if (a[great] < pivot1) {
   1741                         a[k] = a[less];
   1742                         a[less++] = a[great];
   1743                         a[great--] = ak;
   1744                     } else { // pivot1 <= a[great] <= pivot2
   1745                         a[k] = a[great];
   1746                         a[great--] = ak;
   1747                     }
   1748                 }
   1749             }
   1750         } else { // Pivots are equal
   1751             /*
   1752              * Partition degenerates to the traditional 3-way,
   1753              * or "Dutch National Flag", partition:
   1754              *
   1755              *   left part   center part            right part
   1756              * +----------------------------------------------+
   1757              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
   1758              * +----------------------------------------------+
   1759              *              ^            ^       ^
   1760              *              |            |       |
   1761              *             less          k     great
   1762              *
   1763              * Invariants:
   1764              *
   1765              *   all in (left, less)   < pivot
   1766              *   all in [less, k)     == pivot
   1767              *   all in (great, right) > pivot
   1768              *
   1769              * Pointer k is the first index of ?-part
   1770              */
   1771             for (int k = less; k <= great; k++) {
   1772                 float ak = a[k];
   1773                 if (ak == pivot1) {
   1774                     continue;
   1775                 }
   1776                 if (ak < pivot1) { // Move a[k] to left part
   1777                     if (k != less) {
   1778                         a[k] = a[less];
   1779                         a[less] = ak;
   1780                     }
   1781                     less++;
   1782                 } else { // (a[k] > pivot1) -  Move a[k] to right part
   1783                     /*
   1784                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
   1785                      * that great will still be >= k when the following loop
   1786                      * terminates, even though we don't test for it explicitly.
   1787                      * In other words, a[e3] acts as a sentinel for great.
   1788                      */
   1789                     while (a[great] > pivot1) {
   1790                         great--;
   1791                     }
   1792                     if (a[great] < pivot1) {
   1793                         a[k] = a[less];
   1794                         a[less++] = a[great];
   1795                         a[great--] = ak;
   1796                     } else { // a[great] == pivot1
   1797                         a[k] = pivot1;
   1798                         a[great--] = ak;
   1799                     }
   1800                 }
   1801             }
   1802         }
   1803 
   1804         // Swap pivots into their final positions
   1805         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
   1806         a[right] = a[great + 1]; a[great + 1] = pivot2;
   1807 
   1808         // Sort left and right parts recursively, excluding known pivot values
   1809         doSort(a, left,   less - 2);
   1810         doSort(a, great + 2, right);
   1811 
   1812         /*
   1813          * If pivot1 == pivot2, all elements from center
   1814          * part are equal and, therefore, already sorted
   1815          */
   1816         if (!pivotsDiffer) {
   1817             return;
   1818         }
   1819 
   1820         /*
   1821          * If center part is too large (comprises > 2/3 of the array),
   1822          * swap internal pivot values to ends
   1823          */
   1824         if (less < e1 && great > e5) {
   1825             while (a[less] == pivot1) {
   1826                 less++;
   1827             }
   1828             while (a[great] == pivot2) {
   1829                 great--;
   1830             }
   1831 
   1832             /*
   1833              * Partitioning:
   1834              *
   1835              *   left part       center part                   right part
   1836              * +----------------------------------------------------------+
   1837              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
   1838              * +----------------------------------------------------------+
   1839              *              ^                        ^       ^
   1840              *              |                        |       |
   1841              *             less                      k     great
   1842              *
   1843              * Invariants:
   1844              *
   1845              *              all in (*, less)  == pivot1
   1846              *     pivot1 < all in [less, k)   < pivot2
   1847              *              all in (great, *) == pivot2
   1848              *
   1849              * Pointer k is the first index of ?-part
   1850              */
   1851             outer:
   1852             for (int k = less; k <= great; k++) {
   1853                 float ak = a[k];
   1854                 if (ak == pivot2) { // Move a[k] to right part
   1855                     while (a[great] == pivot2) {
   1856                         if (great-- == k) {
   1857                             break outer;
   1858                         }
   1859                     }
   1860                     if (a[great] == pivot1) {
   1861                         a[k] = a[less];
   1862                         a[less++] = pivot1;
   1863                     } else { // pivot1 < a[great] < pivot2
   1864                         a[k] = a[great];
   1865                     }
   1866                     a[great--] = pivot2;
   1867                 } else if (ak == pivot1) { // Move a[k] to left part
   1868                     a[k] = a[less];
   1869                     a[less++] = pivot1;
   1870                 }
   1871             }
   1872         }
   1873 
   1874         // Sort center part recursively, excluding known pivot values
   1875         doSort(a, less, great);
   1876     }
   1877 
   1878     /**
   1879      * Sorts the specified array into ascending numerical order.
   1880      *
   1881      * <p>The {@code <} relation does not provide a total order on all double
   1882      * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
   1883      * value compares neither less than, greater than, nor equal to any value,
   1884      * even itself. This method uses the total order imposed by the method
   1885      * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
   1886      * {@code 0.0d} and {@code Double.NaN} is considered greater than any
   1887      * other value and all {@code Double.NaN} values are considered equal.
   1888      *
   1889      * @param a the array to be sorted
   1890      */
   1891     public static void sort(double[] a) {
   1892         sortNegZeroAndNaN(a, 0, a.length - 1);
   1893     }
   1894 
   1895     /**
   1896      * Sorts the specified range of the array into ascending order. The range
   1897      * to be sorted extends from the index {@code fromIndex}, inclusive, to
   1898      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
   1899      * the range to be sorted is empty (and the call is a no-op).
   1900      *
   1901      * <p>The {@code <} relation does not provide a total order on all double
   1902      * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
   1903      * value compares neither less than, greater than, nor equal to any value,
   1904      * even itself. This method uses the total order imposed by the method
   1905      * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
   1906      * {@code 0.0d} and {@code Double.NaN} is considered greater than any
   1907      * other value and all {@code Double.NaN} values are considered equal.
   1908      *
   1909      * @param a the array to be sorted
   1910      * @param fromIndex the index of the first element, inclusive, to be sorted
   1911      * @param toIndex the index of the last element, exclusive, to be sorted
   1912      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
   1913      * @throws ArrayIndexOutOfBoundsException
   1914      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
   1915      */
   1916     public static void sort(double[] a, int fromIndex, int toIndex) {
   1917         Arrays.checkStartAndEnd(a.length, fromIndex, toIndex);
   1918         sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
   1919     }
   1920 
   1921     /**
   1922      * Sorts the specified range of the array into ascending order. The
   1923      * sort is done in three phases to avoid expensive comparisons in the
   1924      * inner loop. The comparisons would be expensive due to anomalies
   1925      * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
   1926      *
   1927      * @param a the array to be sorted
   1928      * @param left the index of the first element, inclusive, to be sorted
   1929      * @param right the index of the last element, inclusive, to be sorted
   1930      */
   1931     private static void sortNegZeroAndNaN(double[] a, int left, int right) {
   1932         /*
   1933          * Phase 1: Count negative zeros and move NaNs to end of array
   1934          */
   1935         final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
   1936         int numNegativeZeros = 0;
   1937         int n = right;
   1938 
   1939         for (int k = left; k <= n; k++) {
   1940             double ak = a[k];
   1941             if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToRawLongBits(ak)) {
   1942                 a[k] = 0.0d;
   1943                 numNegativeZeros++;
   1944             } else if (ak != ak) { // i.e., ak is NaN
   1945                 a[k--] = a[n];
   1946                 a[n--] = Double.NaN;
   1947             }
   1948         }
   1949 
   1950         /*
   1951          * Phase 2: Sort everything except NaNs (which are already in place)
   1952          */
   1953         doSort(a, left, n);
   1954 
   1955         /*
   1956          * Phase 3: Turn positive zeros back into negative zeros as appropriate
   1957          */
   1958         if (numNegativeZeros == 0) {
   1959             return;
   1960         }
   1961 
   1962         // Find first zero element
   1963         int zeroIndex = findAnyZero(a, left, n);
   1964 
   1965         for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
   1966             zeroIndex = i;
   1967         }
   1968 
   1969         // Turn the right number of positive zeros back into negative zeros
   1970         for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
   1971             a[i] = -0.0d;
   1972         }
   1973     }
   1974 
   1975     /**
   1976      * Returns the index of some zero element in the specified range via
   1977      * binary search. The range is assumed to be sorted, and must contain
   1978      * at least one zero.
   1979      *
   1980      * @param a the array to be searched
   1981      * @param low the index of the first element, inclusive, to be searched
   1982      * @param high the index of the last element, inclusive, to be searched
   1983      */
   1984     private static int findAnyZero(double[] a, int low, int high) {
   1985         while (true) {
   1986             int middle = (low + high) >>> 1;
   1987             double middleValue = a[middle];
   1988 
   1989             if (middleValue < 0.0d) {
   1990                 low = middle + 1;
   1991             } else if (middleValue > 0.0d) {
   1992                 high = middle - 1;
   1993             } else { // middleValue == 0.0d
   1994                 return middle;
   1995             }
   1996         }
   1997     }
   1998 
   1999     /**
   2000      * Sorts the specified range of the array into ascending order. This
   2001      * method differs from the public {@code sort} method in three ways:
   2002      * {@code right} index is inclusive, it does no range checking on
   2003      * {@code left} or {@code right}, and it does not handle negative
   2004      * zeros or NaNs in the array.
   2005      *
   2006      * @param a the array to be sorted, which must not contain -0.0d and NaN
   2007      * @param left the index of the first element, inclusive, to be sorted
   2008      * @param right the index of the last element, inclusive, to be sorted
   2009      */
   2010     private static void doSort(double[] a, int left, int right) {
   2011         // Use insertion sort on tiny arrays
   2012         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
   2013             for (int i = left + 1; i <= right; i++) {
   2014                 double ai = a[i];
   2015                 int j;
   2016                 for (j = i - 1; j >= left && ai < a[j]; j--) {
   2017                     a[j + 1] = a[j];
   2018                 }
   2019                 a[j + 1] = ai;
   2020             }
   2021         } else { // Use Dual-Pivot Quicksort on large arrays
   2022             dualPivotQuicksort(a, left, right);
   2023         }
   2024     }
   2025 
   2026     /**
   2027      * Sorts the specified range of the array into ascending order by the
   2028      * Dual-Pivot Quicksort algorithm.
   2029      *
   2030      * @param a the array to be sorted
   2031      * @param left the index of the first element, inclusive, to be sorted
   2032      * @param right the index of the last element, inclusive, to be sorted
   2033      */
   2034     private static void dualPivotQuicksort(double[] a, int left, int right) {
   2035         // Compute indices of five evenly spaced elements
   2036         int sixth = (right - left + 1) / 6;
   2037         int e1 = left  + sixth;
   2038         int e5 = right - sixth;
   2039         int e3 = (left + right) >>> 1; // The midpoint
   2040         int e4 = e3 + sixth;
   2041         int e2 = e3 - sixth;
   2042 
   2043         // Sort these elements using a 5-element sorting network
   2044         double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
   2045 
   2046         if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
   2047         if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
   2048         if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
   2049         if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
   2050         if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
   2051         if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
   2052         if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
   2053         if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
   2054         if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
   2055 
   2056         a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
   2057 
   2058         /*
   2059          * Use the second and fourth of the five sorted elements as pivots.
   2060          * These values are inexpensive approximations of the first and
   2061          * second terciles of the array. Note that pivot1 <= pivot2.
   2062          *
   2063          * The pivots are stored in local variables, and the first and
   2064          * the last of the elements to be sorted are moved to the locations
   2065          * formerly occupied by the pivots. When partitioning is complete,
   2066          * the pivots are swapped back into their final positions, and
   2067          * excluded from subsequent sorting.
   2068          */
   2069         double pivot1 = ae2; a[e2] = a[left];
   2070         double pivot2 = ae4; a[e4] = a[right];
   2071 
   2072         // Pointers
   2073         int less  = left  + 1; // The index of first element of center part
   2074         int great = right - 1; // The index before first element of right part
   2075 
   2076         boolean pivotsDiffer = (pivot1 != pivot2);
   2077 
   2078         if (pivotsDiffer) {
   2079             /*
   2080              * Partitioning:
   2081              *
   2082              *   left part         center part                    right part
   2083              * +------------------------------------------------------------+
   2084              * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
   2085              * +------------------------------------------------------------+
   2086              *              ^                          ^       ^
   2087              *              |                          |       |
   2088              *             less                        k     great
   2089              *
   2090              * Invariants:
   2091              *
   2092              *              all in (left, less)   < pivot1
   2093              *    pivot1 <= all in [less, k)     <= pivot2
   2094              *              all in (great, right) > pivot2
   2095              *
   2096              * Pointer k is the first index of ?-part
   2097              */
   2098             outer:
   2099             for (int k = less; k <= great; k++) {
   2100                 double ak = a[k];
   2101                 if (ak < pivot1) { // Move a[k] to left part
   2102                     if (k != less) {
   2103                         a[k] = a[less];
   2104                         a[less] = ak;
   2105                     }
   2106                     less++;
   2107                 } else if (ak > pivot2) { // Move a[k] to right part
   2108                     while (a[great] > pivot2) {
   2109                         if (great-- == k) {
   2110                             break outer;
   2111                         }
   2112                     }
   2113                     if (a[great] < pivot1) {
   2114                         a[k] = a[less];
   2115                         a[less++] = a[great];
   2116                         a[great--] = ak;
   2117                     } else { // pivot1 <= a[great] <= pivot2
   2118                         a[k] = a[great];
   2119                         a[great--] = ak;
   2120                     }
   2121                 }
   2122             }
   2123         } else { // Pivots are equal
   2124             /*
   2125              * Partition degenerates to the traditional 3-way,
   2126              * or "Dutch National Flag", partition:
   2127              *
   2128              *   left part   center part            right part
   2129              * +----------------------------------------------+
   2130              * |  < pivot  |  == pivot  |    ?    |  > pivot  |
   2131              * +----------------------------------------------+
   2132              *              ^            ^       ^
   2133              *              |            |       |
   2134              *             less          k     great
   2135              *
   2136              * Invariants:
   2137              *
   2138              *   all in (left, less)   < pivot
   2139              *   all in [less, k)     == pivot
   2140              *   all in (great, right) > pivot
   2141              *
   2142              * Pointer k is the first index of ?-part
   2143              */
   2144             for (int k = less; k <= great; k++) {
   2145                 double ak = a[k];
   2146                 if (ak == pivot1) {
   2147                     continue;
   2148                 }
   2149                 if (ak < pivot1) { // Move a[k] to left part
   2150                     if (k != less) {
   2151                         a[k] = a[less];
   2152                         a[less] = ak;
   2153                     }
   2154                     less++;
   2155                 } else { // (a[k] > pivot1) -  Move a[k] to right part
   2156                     /*
   2157                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
   2158                      * that great will still be >= k when the following loop
   2159                      * terminates, even though we don't test for it explicitly.
   2160                      * In other words, a[e3] acts as a sentinel for great.
   2161                      */
   2162                     while (a[great] > pivot1) {
   2163                         great--;
   2164                     }
   2165                     if (a[great] < pivot1) {
   2166                         a[k] = a[less];
   2167                         a[less++] = a[great];
   2168                         a[great--] = ak;
   2169                     } else { // a[great] == pivot1
   2170                         a[k] = pivot1;
   2171                         a[great--] = ak;
   2172                     }
   2173                 }
   2174             }
   2175         }
   2176 
   2177         // Swap pivots into their final positions
   2178         a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
   2179         a[right] = a[great + 1]; a[great + 1] = pivot2;
   2180 
   2181         // Sort left and right parts recursively, excluding known pivot values
   2182         doSort(a, left,   less - 2);
   2183         doSort(a, great + 2, right);
   2184 
   2185         /*
   2186          * If pivot1 == pivot2, all elements from center
   2187          * part are equal and, therefore, already sorted
   2188          */
   2189         if (!pivotsDiffer) {
   2190             return;
   2191         }
   2192 
   2193         /*
   2194          * If center part is too large (comprises > 2/3 of the array),
   2195          * swap internal pivot values to ends
   2196          */
   2197         if (less < e1 && great > e5) {
   2198             while (a[less] == pivot1) {
   2199                 less++;
   2200             }
   2201             while (a[great] == pivot2) {
   2202                 great--;
   2203             }
   2204 
   2205             /*
   2206              * Partitioning:
   2207              *
   2208              *   left part       center part                   right part
   2209              * +----------------------------------------------------------+
   2210              * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
   2211              * +----------------------------------------------------------+
   2212              *              ^                        ^       ^
   2213              *              |                        |       |
   2214              *             less                      k     great
   2215              *
   2216              * Invariants:
   2217              *
   2218              *              all in (*, less)  == pivot1
   2219              *     pivot1 < all in [less, k)   < pivot2
   2220              *              all in (great, *) == pivot2
   2221              *
   2222              * Pointer k is the first index of ?-part
   2223              */
   2224             outer:
   2225             for (int k = less; k <= great; k++) {
   2226                 double ak = a[k];
   2227                 if (ak == pivot2) { // Move a[k] to right part
   2228                     while (a[great] == pivot2) {
   2229                         if (great-- == k) {
   2230                             break outer;
   2231                         }
   2232                     }
   2233                     if (a[great] == pivot1) {
   2234                         a[k] = a[less];
   2235                         a[less++] = pivot1;
   2236                     } else { // pivot1 < a[great] < pivot2
   2237                         a[k] = a[great];
   2238                     }
   2239                     a[great--] = pivot2;
   2240                 } else if (ak == pivot1) { // Move a[k] to left part
   2241                     a[k] = a[less];
   2242                     a[less++] = pivot1;
   2243                 }
   2244             }
   2245         }
   2246 
   2247         // Sort center part recursively, excluding known pivot values
   2248         doSort(a, less, great);
   2249     }
   2250 }
   2251