Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    1   /*
    2    * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.util;
   27   
   28   /**
   29    * This class implements the Dual-Pivot Quicksort algorithm by
   30    * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
   31    * offers O(n log(n)) performance on many data sets that cause other
   32    * quicksorts to degrade to quadratic performance, and is typically
   33    * faster than traditional (one-pivot) Quicksort implementations.
   34    *
   35    * @author Vladimir Yaroslavskiy
   36    * @author Jon Bentley
   37    * @author Josh Bloch
   38    *
   39    * @version 2011.02.11 m765.827.12i:5\7pm
   40    * @since 1.7
   41    */
   42   final class DualPivotQuicksort {
   43   
   44       /**
   45        * Prevents instantiation.
   46        */
   47       private DualPivotQuicksort() {}
   48   
   49       /*
   50        * Tuning parameters.
   51        */
   52   
   53       /**
   54        * The maximum number of runs in merge sort.
   55        */
   56       private static final int MAX_RUN_COUNT = 67;
   57   
   58       /**
   59        * The maximum length of run in merge sort.
   60        */
   61       private static final int MAX_RUN_LENGTH = 33;
   62   
   63       /**
   64        * If the length of an array to be sorted is less than this
   65        * constant, Quicksort is used in preference to merge sort.
   66        */
   67       private static final int QUICKSORT_THRESHOLD = 286;
   68   
   69       /**
   70        * If the length of an array to be sorted is less than this
   71        * constant, insertion sort is used in preference to Quicksort.
   72        */
   73       private static final int INSERTION_SORT_THRESHOLD = 47;
   74   
   75       /**
   76        * If the length of a byte array to be sorted is greater than this
   77        * constant, counting sort is used in preference to insertion sort.
   78        */
   79       private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
   80   
   81       /**
   82        * If the length of a short or char array to be sorted is greater
   83        * than this constant, counting sort is used in preference to Quicksort.
   84        */
   85       private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
   86   
   87       /*
   88        * Sorting methods for seven primitive types.
   89        */
   90   
   91       /**
   92        * Sorts the specified array.
   93        *
   94        * @param a the array to be sorted
   95        */
   96       public static void sort(int[] a) {
   97           sort(a, 0, a.length - 1);
   98       }
   99   
  100       /**
  101        * Sorts the specified range of the array.
  102        *
  103        * @param a the array to be sorted
  104        * @param left the index of the first element, inclusive, to be sorted
  105        * @param right the index of the last element, inclusive, to be sorted
  106        */
  107       public static void sort(int[] a, int left, int right) {
  108           // Use Quicksort on small arrays
  109           if (right - left < QUICKSORT_THRESHOLD) {
  110               sort(a, left, right, true);
  111               return;
  112           }
  113   
  114           /*
  115            * Index run[i] is the start of i-th run
  116            * (ascending or descending sequence).
  117            */
  118           int[] run = new int[MAX_RUN_COUNT + 1];
  119           int count = 0; run[0] = left;
  120   
  121           // Check if the array is nearly sorted
  122           for (int k = left; k < right; run[count] = k) {
  123               if (a[k] < a[k + 1]) { // ascending
  124                   while (++k <= right && a[k - 1] <= a[k]);
  125               } else if (a[k] > a[k + 1]) { // descending
  126                   while (++k <= right && a[k - 1] >= a[k]);
  127                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  128                       int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  129                   }
  130               } else { // equal
  131                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  132                       if (--m == 0) {
  133                           sort(a, left, right, true);
  134                           return;
  135                       }
  136                   }
  137               }
  138   
  139               /*
  140                * The array is not highly structured,
  141                * use Quicksort instead of merge sort.
  142                */
  143               if (++count == MAX_RUN_COUNT) {
  144                   sort(a, left, right, true);
  145                   return;
  146               }
  147           }
  148   
  149           // Check special cases
  150           if (run[count] == right++) { // The last run contains one element
  151               run[++count] = right;
  152           } else if (count == 1) { // The array is already sorted
  153               return;
  154           }
  155   
  156           /*
  157            * Create temporary array, which is used for merging.
  158            * Implementation note: variable "right" is increased by 1.
  159            */
  160           int[] b; byte odd = 0;
  161           for (int n = 1; (n <<= 1) < count; odd ^= 1);
  162   
  163           if (odd == 0) {
  164               b = a; a = new int[b.length];
  165               for (int i = left - 1; ++i < right; a[i] = b[i]);
  166           } else {
  167               b = new int[a.length];
  168           }
  169   
  170           // Merging
  171           for (int last; count > 1; count = last) {
  172               for (int k = (last = 0) + 2; k <= count; k += 2) {
  173                   int hi = run[k], mi = run[k - 1];
  174                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  175                       if (q >= hi || p < mi && a[p] <= a[q]) {
  176                           b[i] = a[p++];
  177                       } else {
  178                           b[i] = a[q++];
  179                       }
  180                   }
  181                   run[++last] = hi;
  182               }
  183               if ((count & 1) != 0) {
  184                   for (int i = right, lo = run[count - 1]; --i >= lo;
  185                       b[i] = a[i]
  186                   );
  187                   run[++last] = right;
  188               }
  189               int[] t = a; a = b; b = t;
  190           }
  191       }
  192   
  193       /**
  194        * Sorts the specified range of the array by Dual-Pivot Quicksort.
  195        *
  196        * @param a the array to be sorted
  197        * @param left the index of the first element, inclusive, to be sorted
  198        * @param right the index of the last element, inclusive, to be sorted
  199        * @param leftmost indicates if this part is the leftmost in the range
  200        */
  201       private static void sort(int[] a, int left, int right, boolean leftmost) {
  202           int length = right - left + 1;
  203   
  204           // Use insertion sort on tiny arrays
  205           if (length < INSERTION_SORT_THRESHOLD) {
  206               if (leftmost) {
  207                   /*
  208                    * Traditional (without sentinel) insertion sort,
  209                    * optimized for server VM, is used in case of
  210                    * the leftmost part.
  211                    */
  212                   for (int i = left, j = i; i < right; j = ++i) {
  213                       int ai = a[i + 1];
  214                       while (ai < a[j]) {
  215                           a[j + 1] = a[j];
  216                           if (j-- == left) {
  217                               break;
  218                           }
  219                       }
  220                       a[j + 1] = ai;
  221                   }
  222               } else {
  223                   /*
  224                    * Skip the longest ascending sequence.
  225                    */
  226                   do {
  227                       if (left >= right) {
  228                           return;
  229                       }
  230                   } while (a[++left] >= a[left - 1]);
  231   
  232                   /*
  233                    * Every element from adjoining part plays the role
  234                    * of sentinel, therefore this allows us to avoid the
  235                    * left range check on each iteration. Moreover, we use
  236                    * the more optimized algorithm, so called pair insertion
  237                    * sort, which is faster (in the context of Quicksort)
  238                    * than traditional implementation of insertion sort.
  239                    */
  240                   for (int k = left; ++left <= right; k = ++left) {
  241                       int a1 = a[k], a2 = a[left];
  242   
  243                       if (a1 < a2) {
  244                           a2 = a1; a1 = a[left];
  245                       }
  246                       while (a1 < a[--k]) {
  247                           a[k + 2] = a[k];
  248                       }
  249                       a[++k + 1] = a1;
  250   
  251                       while (a2 < a[--k]) {
  252                           a[k + 1] = a[k];
  253                       }
  254                       a[k + 1] = a2;
  255                   }
  256                   int last = a[right];
  257   
  258                   while (last < a[--right]) {
  259                       a[right + 1] = a[right];
  260                   }
  261                   a[right + 1] = last;
  262               }
  263               return;
  264           }
  265   
  266           // Inexpensive approximation of length / 7
  267           int seventh = (length >> 3) + (length >> 6) + 1;
  268   
  269           /*
  270            * Sort five evenly spaced elements around (and including) the
  271            * center element in the range. These elements will be used for
  272            * pivot selection as described below. The choice for spacing
  273            * these elements was empirically determined to work well on
  274            * a wide variety of inputs.
  275            */
  276           int e3 = (left + right) >>> 1; // The midpoint
  277           int e2 = e3 - seventh;
  278           int e1 = e2 - seventh;
  279           int e4 = e3 + seventh;
  280           int e5 = e4 + seventh;
  281   
  282           // Sort these elements using insertion sort
  283           if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  284   
  285           if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  286               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  287           }
  288           if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  289               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  290                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  291               }
  292           }
  293           if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  294               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  295                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  296                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  297                   }
  298               }
  299           }
  300   
  301           // Pointers
  302           int less  = left;  // The index of the first element of center part
  303           int great = right; // The index before the first element of right part
  304   
  305           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  306               /*
  307                * Use the second and fourth of the five sorted elements as pivots.
  308                * These values are inexpensive approximations of the first and
  309                * second terciles of the array. Note that pivot1 <= pivot2.
  310                */
  311               int pivot1 = a[e2];
  312               int pivot2 = a[e4];
  313   
  314               /*
  315                * The first and the last elements to be sorted are moved to the
  316                * locations formerly occupied by the pivots. When partitioning
  317                * is complete, the pivots are swapped back into their final
  318                * positions, and excluded from subsequent sorting.
  319                */
  320               a[e2] = a[left];
  321               a[e4] = a[right];
  322   
  323               /*
  324                * Skip elements, which are less or greater than pivot values.
  325                */
  326               while (a[++less] < pivot1);
  327               while (a[--great] > pivot2);
  328   
  329               /*
  330                * Partitioning:
  331                *
  332                *   left part           center part                   right part
  333                * +--------------------------------------------------------------+
  334                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  335                * +--------------------------------------------------------------+
  336                *               ^                          ^       ^
  337                *               |                          |       |
  338                *              less                        k     great
  339                *
  340                * Invariants:
  341                *
  342                *              all in (left, less)   < pivot1
  343                *    pivot1 <= all in [less, k)     <= pivot2
  344                *              all in (great, right) > pivot2
  345                *
  346                * Pointer k is the first index of ?-part.
  347                */
  348               outer:
  349               for (int k = less - 1; ++k <= great; ) {
  350                   int ak = a[k];
  351                   if (ak < pivot1) { // Move a[k] to left part
  352                       a[k] = a[less];
  353                       /*
  354                        * Here and below we use "a[i] = b; i++;" instead
  355                        * of "a[i++] = b;" due to performance issue.
  356                        */
  357                       a[less] = ak;
  358                       ++less;
  359                   } else if (ak > pivot2) { // Move a[k] to right part
  360                       while (a[great] > pivot2) {
  361                           if (great-- == k) {
  362                               break outer;
  363                           }
  364                       }
  365                       if (a[great] < pivot1) { // a[great] <= pivot2
  366                           a[k] = a[less];
  367                           a[less] = a[great];
  368                           ++less;
  369                       } else { // pivot1 <= a[great] <= pivot2
  370                           a[k] = a[great];
  371                       }
  372                       /*
  373                        * Here and below we use "a[i] = b; i--;" instead
  374                        * of "a[i--] = b;" due to performance issue.
  375                        */
  376                       a[great] = ak;
  377                       --great;
  378                   }
  379               }
  380   
  381               // Swap pivots into their final positions
  382               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  383               a[right] = a[great + 1]; a[great + 1] = pivot2;
  384   
  385               // Sort left and right parts recursively, excluding known pivots
  386               sort(a, left, less - 2, leftmost);
  387               sort(a, great + 2, right, false);
  388   
  389               /*
  390                * If center part is too large (comprises > 4/7 of the array),
  391                * swap internal pivot values to ends.
  392                */
  393               if (less < e1 && e5 < great) {
  394                   /*
  395                    * Skip elements, which are equal to pivot values.
  396                    */
  397                   while (a[less] == pivot1) {
  398                       ++less;
  399                   }
  400   
  401                   while (a[great] == pivot2) {
  402                       --great;
  403                   }
  404   
  405                   /*
  406                    * Partitioning:
  407                    *
  408                    *   left part         center part                  right part
  409                    * +----------------------------------------------------------+
  410                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  411                    * +----------------------------------------------------------+
  412                    *              ^                        ^       ^
  413                    *              |                        |       |
  414                    *             less                      k     great
  415                    *
  416                    * Invariants:
  417                    *
  418                    *              all in (*,  less) == pivot1
  419                    *     pivot1 < all in [less,  k)  < pivot2
  420                    *              all in (great, *) == pivot2
  421                    *
  422                    * Pointer k is the first index of ?-part.
  423                    */
  424                   outer:
  425                   for (int k = less - 1; ++k <= great; ) {
  426                       int ak = a[k];
  427                       if (ak == pivot1) { // Move a[k] to left part
  428                           a[k] = a[less];
  429                           a[less] = ak;
  430                           ++less;
  431                       } else if (ak == pivot2) { // Move a[k] to right part
  432                           while (a[great] == pivot2) {
  433                               if (great-- == k) {
  434                                   break outer;
  435                               }
  436                           }
  437                           if (a[great] == pivot1) { // a[great] < pivot2
  438                               a[k] = a[less];
  439                               /*
  440                                * Even though a[great] equals to pivot1, the
  441                                * assignment a[less] = pivot1 may be incorrect,
  442                                * if a[great] and pivot1 are floating-point zeros
  443                                * of different signs. Therefore in float and
  444                                * double sorting methods we have to use more
  445                                * accurate assignment a[less] = a[great].
  446                                */
  447                               a[less] = pivot1;
  448                               ++less;
  449                           } else { // pivot1 < a[great] < pivot2
  450                               a[k] = a[great];
  451                           }
  452                           a[great] = ak;
  453                           --great;
  454                       }
  455                   }
  456               }
  457   
  458               // Sort center part recursively
  459               sort(a, less, great, false);
  460   
  461           } else { // Partitioning with one pivot
  462               /*
  463                * Use the third of the five sorted elements as pivot.
  464                * This value is inexpensive approximation of the median.
  465                */
  466               int pivot = a[e3];
  467   
  468               /*
  469                * Partitioning degenerates to the traditional 3-way
  470                * (or "Dutch National Flag") schema:
  471                *
  472                *   left part    center part              right part
  473                * +-------------------------------------------------+
  474                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  475                * +-------------------------------------------------+
  476                *              ^              ^        ^
  477                *              |              |        |
  478                *             less            k      great
  479                *
  480                * Invariants:
  481                *
  482                *   all in (left, less)   < pivot
  483                *   all in [less, k)     == pivot
  484                *   all in (great, right) > pivot
  485                *
  486                * Pointer k is the first index of ?-part.
  487                */
  488               for (int k = less; k <= great; ++k) {
  489                   if (a[k] == pivot) {
  490                       continue;
  491                   }
  492                   int ak = a[k];
  493                   if (ak < pivot) { // Move a[k] to left part
  494                       a[k] = a[less];
  495                       a[less] = ak;
  496                       ++less;
  497                   } else { // a[k] > pivot - Move a[k] to right part
  498                       while (a[great] > pivot) {
  499                           --great;
  500                       }
  501                       if (a[great] < pivot) { // a[great] <= pivot
  502                           a[k] = a[less];
  503                           a[less] = a[great];
  504                           ++less;
  505                       } else { // a[great] == pivot
  506                           /*
  507                            * Even though a[great] equals to pivot, the
  508                            * assignment a[k] = pivot may be incorrect,
  509                            * if a[great] and pivot are floating-point
  510                            * zeros of different signs. Therefore in float
  511                            * and double sorting methods we have to use
  512                            * more accurate assignment a[k] = a[great].
  513                            */
  514                           a[k] = pivot;
  515                       }
  516                       a[great] = ak;
  517                       --great;
  518                   }
  519               }
  520   
  521               /*
  522                * Sort left and right parts recursively.
  523                * All elements from center part are equal
  524                * and, therefore, already sorted.
  525                */
  526               sort(a, left, less - 1, leftmost);
  527               sort(a, great + 1, right, false);
  528           }
  529       }
  530   
  531       /**
  532        * Sorts the specified array.
  533        *
  534        * @param a the array to be sorted
  535        */
  536       public static void sort(long[] a) {
  537           sort(a, 0, a.length - 1);
  538       }
  539   
  540       /**
  541        * Sorts the specified range of the array.
  542        *
  543        * @param a the array to be sorted
  544        * @param left the index of the first element, inclusive, to be sorted
  545        * @param right the index of the last element, inclusive, to be sorted
  546        */
  547       public static void sort(long[] a, int left, int right) {
  548           // Use Quicksort on small arrays
  549           if (right - left < QUICKSORT_THRESHOLD) {
  550               sort(a, left, right, true);
  551               return;
  552           }
  553   
  554           /*
  555            * Index run[i] is the start of i-th run
  556            * (ascending or descending sequence).
  557            */
  558           int[] run = new int[MAX_RUN_COUNT + 1];
  559           int count = 0; run[0] = left;
  560   
  561           // Check if the array is nearly sorted
  562           for (int k = left; k < right; run[count] = k) {
  563               if (a[k] < a[k + 1]) { // ascending
  564                   while (++k <= right && a[k - 1] <= a[k]);
  565               } else if (a[k] > a[k + 1]) { // descending
  566                   while (++k <= right && a[k - 1] >= a[k]);
  567                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  568                       long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  569                   }
  570               } else { // equal
  571                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  572                       if (--m == 0) {
  573                           sort(a, left, right, true);
  574                           return;
  575                       }
  576                   }
  577               }
  578   
  579               /*
  580                * The array is not highly structured,
  581                * use Quicksort instead of merge sort.
  582                */
  583               if (++count == MAX_RUN_COUNT) {
  584                   sort(a, left, right, true);
  585                   return;
  586               }
  587           }
  588   
  589           // Check special cases
  590           if (run[count] == right++) { // The last run contains one element
  591               run[++count] = right;
  592           } else if (count == 1) { // The array is already sorted
  593               return;
  594           }
  595   
  596           /*
  597            * Create temporary array, which is used for merging.
  598            * Implementation note: variable "right" is increased by 1.
  599            */
  600           long[] b; byte odd = 0;
  601           for (int n = 1; (n <<= 1) < count; odd ^= 1);
  602   
  603           if (odd == 0) {
  604               b = a; a = new long[b.length];
  605               for (int i = left - 1; ++i < right; a[i] = b[i]);
  606           } else {
  607               b = new long[a.length];
  608           }
  609   
  610           // Merging
  611           for (int last; count > 1; count = last) {
  612               for (int k = (last = 0) + 2; k <= count; k += 2) {
  613                   int hi = run[k], mi = run[k - 1];
  614                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  615                       if (q >= hi || p < mi && a[p] <= a[q]) {
  616                           b[i] = a[p++];
  617                       } else {
  618                           b[i] = a[q++];
  619                       }
  620                   }
  621                   run[++last] = hi;
  622               }
  623               if ((count & 1) != 0) {
  624                   for (int i = right, lo = run[count - 1]; --i >= lo;
  625                       b[i] = a[i]
  626                   );
  627                   run[++last] = right;
  628               }
  629               long[] t = a; a = b; b = t;
  630           }
  631       }
  632   
  633       /**
  634        * Sorts the specified range of the array by Dual-Pivot Quicksort.
  635        *
  636        * @param a the array to be sorted
  637        * @param left the index of the first element, inclusive, to be sorted
  638        * @param right the index of the last element, inclusive, to be sorted
  639        * @param leftmost indicates if this part is the leftmost in the range
  640        */
  641       private static void sort(long[] a, int left, int right, boolean leftmost) {
  642           int length = right - left + 1;
  643   
  644           // Use insertion sort on tiny arrays
  645           if (length < INSERTION_SORT_THRESHOLD) {
  646               if (leftmost) {
  647                   /*
  648                    * Traditional (without sentinel) insertion sort,
  649                    * optimized for server VM, is used in case of
  650                    * the leftmost part.
  651                    */
  652                   for (int i = left, j = i; i < right; j = ++i) {
  653                       long ai = a[i + 1];
  654                       while (ai < a[j]) {
  655                           a[j + 1] = a[j];
  656                           if (j-- == left) {
  657                               break;
  658                           }
  659                       }
  660                       a[j + 1] = ai;
  661                   }
  662               } else {
  663                   /*
  664                    * Skip the longest ascending sequence.
  665                    */
  666                   do {
  667                       if (left >= right) {
  668                           return;
  669                       }
  670                   } while (a[++left] >= a[left - 1]);
  671   
  672                   /*
  673                    * Every element from adjoining part plays the role
  674                    * of sentinel, therefore this allows us to avoid the
  675                    * left range check on each iteration. Moreover, we use
  676                    * the more optimized algorithm, so called pair insertion
  677                    * sort, which is faster (in the context of Quicksort)
  678                    * than traditional implementation of insertion sort.
  679                    */
  680                   for (int k = left; ++left <= right; k = ++left) {
  681                       long a1 = a[k], a2 = a[left];
  682   
  683                       if (a1 < a2) {
  684                           a2 = a1; a1 = a[left];
  685                       }
  686                       while (a1 < a[--k]) {
  687                           a[k + 2] = a[k];
  688                       }
  689                       a[++k + 1] = a1;
  690   
  691                       while (a2 < a[--k]) {
  692                           a[k + 1] = a[k];
  693                       }
  694                       a[k + 1] = a2;
  695                   }
  696                   long last = a[right];
  697   
  698                   while (last < a[--right]) {
  699                       a[right + 1] = a[right];
  700                   }
  701                   a[right + 1] = last;
  702               }
  703               return;
  704           }
  705   
  706           // Inexpensive approximation of length / 7
  707           int seventh = (length >> 3) + (length >> 6) + 1;
  708   
  709           /*
  710            * Sort five evenly spaced elements around (and including) the
  711            * center element in the range. These elements will be used for
  712            * pivot selection as described below. The choice for spacing
  713            * these elements was empirically determined to work well on
  714            * a wide variety of inputs.
  715            */
  716           int e3 = (left + right) >>> 1; // The midpoint
  717           int e2 = e3 - seventh;
  718           int e1 = e2 - seventh;
  719           int e4 = e3 + seventh;
  720           int e5 = e4 + seventh;
  721   
  722           // Sort these elements using insertion sort
  723           if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  724   
  725           if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  726               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  727           }
  728           if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  729               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  730                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  731               }
  732           }
  733           if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  734               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  735                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  736                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  737                   }
  738               }
  739           }
  740   
  741           // Pointers
  742           int less  = left;  // The index of the first element of center part
  743           int great = right; // The index before the first element of right part
  744   
  745           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  746               /*
  747                * Use the second and fourth of the five sorted elements as pivots.
  748                * These values are inexpensive approximations of the first and
  749                * second terciles of the array. Note that pivot1 <= pivot2.
  750                */
  751               long pivot1 = a[e2];
  752               long pivot2 = a[e4];
  753   
  754               /*
  755                * The first and the last elements to be sorted are moved to the
  756                * locations formerly occupied by the pivots. When partitioning
  757                * is complete, the pivots are swapped back into their final
  758                * positions, and excluded from subsequent sorting.
  759                */
  760               a[e2] = a[left];
  761               a[e4] = a[right];
  762   
  763               /*
  764                * Skip elements, which are less or greater than pivot values.
  765                */
  766               while (a[++less] < pivot1);
  767               while (a[--great] > pivot2);
  768   
  769               /*
  770                * Partitioning:
  771                *
  772                *   left part           center part                   right part
  773                * +--------------------------------------------------------------+
  774                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  775                * +--------------------------------------------------------------+
  776                *               ^                          ^       ^
  777                *               |                          |       |
  778                *              less                        k     great
  779                *
  780                * Invariants:
  781                *
  782                *              all in (left, less)   < pivot1
  783                *    pivot1 <= all in [less, k)     <= pivot2
  784                *              all in (great, right) > pivot2
  785                *
  786                * Pointer k is the first index of ?-part.
  787                */
  788               outer:
  789               for (int k = less - 1; ++k <= great; ) {
  790                   long ak = a[k];
  791                   if (ak < pivot1) { // Move a[k] to left part
  792                       a[k] = a[less];
  793                       /*
  794                        * Here and below we use "a[i] = b; i++;" instead
  795                        * of "a[i++] = b;" due to performance issue.
  796                        */
  797                       a[less] = ak;
  798                       ++less;
  799                   } else if (ak > pivot2) { // Move a[k] to right part
  800                       while (a[great] > pivot2) {
  801                           if (great-- == k) {
  802                               break outer;
  803                           }
  804                       }
  805                       if (a[great] < pivot1) { // a[great] <= pivot2
  806                           a[k] = a[less];
  807                           a[less] = a[great];
  808                           ++less;
  809                       } else { // pivot1 <= a[great] <= pivot2
  810                           a[k] = a[great];
  811                       }
  812                       /*
  813                        * Here and below we use "a[i] = b; i--;" instead
  814                        * of "a[i--] = b;" due to performance issue.
  815                        */
  816                       a[great] = ak;
  817                       --great;
  818                   }
  819               }
  820   
  821               // Swap pivots into their final positions
  822               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  823               a[right] = a[great + 1]; a[great + 1] = pivot2;
  824   
  825               // Sort left and right parts recursively, excluding known pivots
  826               sort(a, left, less - 2, leftmost);
  827               sort(a, great + 2, right, false);
  828   
  829               /*
  830                * If center part is too large (comprises > 4/7 of the array),
  831                * swap internal pivot values to ends.
  832                */
  833               if (less < e1 && e5 < great) {
  834                   /*
  835                    * Skip elements, which are equal to pivot values.
  836                    */
  837                   while (a[less] == pivot1) {
  838                       ++less;
  839                   }
  840   
  841                   while (a[great] == pivot2) {
  842                       --great;
  843                   }
  844   
  845                   /*
  846                    * Partitioning:
  847                    *
  848                    *   left part         center part                  right part
  849                    * +----------------------------------------------------------+
  850                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  851                    * +----------------------------------------------------------+
  852                    *              ^                        ^       ^
  853                    *              |                        |       |
  854                    *             less                      k     great
  855                    *
  856                    * Invariants:
  857                    *
  858                    *              all in (*,  less) == pivot1
  859                    *     pivot1 < all in [less,  k)  < pivot2
  860                    *              all in (great, *) == pivot2
  861                    *
  862                    * Pointer k is the first index of ?-part.
  863                    */
  864                   outer:
  865                   for (int k = less - 1; ++k <= great; ) {
  866                       long ak = a[k];
  867                       if (ak == pivot1) { // Move a[k] to left part
  868                           a[k] = a[less];
  869                           a[less] = ak;
  870                           ++less;
  871                       } else if (ak == pivot2) { // Move a[k] to right part
  872                           while (a[great] == pivot2) {
  873                               if (great-- == k) {
  874                                   break outer;
  875                               }
  876                           }
  877                           if (a[great] == pivot1) { // a[great] < pivot2
  878                               a[k] = a[less];
  879                               /*
  880                                * Even though a[great] equals to pivot1, the
  881                                * assignment a[less] = pivot1 may be incorrect,
  882                                * if a[great] and pivot1 are floating-point zeros
  883                                * of different signs. Therefore in float and
  884                                * double sorting methods we have to use more
  885                                * accurate assignment a[less] = a[great].
  886                                */
  887                               a[less] = pivot1;
  888                               ++less;
  889                           } else { // pivot1 < a[great] < pivot2
  890                               a[k] = a[great];
  891                           }
  892                           a[great] = ak;
  893                           --great;
  894                       }
  895                   }
  896               }
  897   
  898               // Sort center part recursively
  899               sort(a, less, great, false);
  900   
  901           } else { // Partitioning with one pivot
  902               /*
  903                * Use the third of the five sorted elements as pivot.
  904                * This value is inexpensive approximation of the median.
  905                */
  906               long pivot = a[e3];
  907   
  908               /*
  909                * Partitioning degenerates to the traditional 3-way
  910                * (or "Dutch National Flag") schema:
  911                *
  912                *   left part    center part              right part
  913                * +-------------------------------------------------+
  914                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  915                * +-------------------------------------------------+
  916                *              ^              ^        ^
  917                *              |              |        |
  918                *             less            k      great
  919                *
  920                * Invariants:
  921                *
  922                *   all in (left, less)   < pivot
  923                *   all in [less, k)     == pivot
  924                *   all in (great, right) > pivot
  925                *
  926                * Pointer k is the first index of ?-part.
  927                */
  928               for (int k = less; k <= great; ++k) {
  929                   if (a[k] == pivot) {
  930                       continue;
  931                   }
  932                   long ak = a[k];
  933                   if (ak < pivot) { // Move a[k] to left part
  934                       a[k] = a[less];
  935                       a[less] = ak;
  936                       ++less;
  937                   } else { // a[k] > pivot - Move a[k] to right part
  938                       while (a[great] > pivot) {
  939                           --great;
  940                       }
  941                       if (a[great] < pivot) { // a[great] <= pivot
  942                           a[k] = a[less];
  943                           a[less] = a[great];
  944                           ++less;
  945                       } else { // a[great] == pivot
  946                           /*
  947                            * Even though a[great] equals to pivot, the
  948                            * assignment a[k] = pivot may be incorrect,
  949                            * if a[great] and pivot are floating-point
  950                            * zeros of different signs. Therefore in float
  951                            * and double sorting methods we have to use
  952                            * more accurate assignment a[k] = a[great].
  953                            */
  954                           a[k] = pivot;
  955                       }
  956                       a[great] = ak;
  957                       --great;
  958                   }
  959               }
  960   
  961               /*
  962                * Sort left and right parts recursively.
  963                * All elements from center part are equal
  964                * and, therefore, already sorted.
  965                */
  966               sort(a, left, less - 1, leftmost);
  967               sort(a, great + 1, right, false);
  968           }
  969       }
  970   
  971       /**
  972        * Sorts the specified array.
  973        *
  974        * @param a the array to be sorted
  975        */
  976       public static void sort(short[] a) {
  977           sort(a, 0, a.length - 1);
  978       }
  979   
  980       /**
  981        * Sorts the specified range of the array.
  982        *
  983        * @param a the array to be sorted
  984        * @param left the index of the first element, inclusive, to be sorted
  985        * @param right the index of the last element, inclusive, to be sorted
  986        */
  987       public static void sort(short[] a, int left, int right) {
  988           // Use counting sort on large arrays
  989           if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
  990               int[] count = new int[NUM_SHORT_VALUES];
  991   
  992               for (int i = left - 1; ++i <= right;
  993                   count[a[i] - Short.MIN_VALUE]++
  994               );
  995               for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
  996                   while (count[--i] == 0);
  997                   short value = (short) (i + Short.MIN_VALUE);
  998                   int s = count[i];
  999   
 1000                   do {
 1001                       a[--k] = value;
 1002                   } while (--s > 0);
 1003               }
 1004           } else { // Use Dual-Pivot Quicksort on small arrays
 1005               doSort(a, left, right);
 1006           }
 1007       }
 1008   
 1009       /** The number of distinct short values. */
 1010       private static final int NUM_SHORT_VALUES = 1 << 16;
 1011   
 1012       /**
 1013        * Sorts the specified range of the array.
 1014        *
 1015        * @param a the array to be sorted
 1016        * @param left the index of the first element, inclusive, to be sorted
 1017        * @param right the index of the last element, inclusive, to be sorted
 1018        */
 1019       private static void doSort(short[] a, int left, int right) {
 1020           // Use Quicksort on small arrays
 1021           if (right - left < QUICKSORT_THRESHOLD) {
 1022               sort(a, left, right, true);
 1023               return;
 1024           }
 1025   
 1026           /*
 1027            * Index run[i] is the start of i-th run
 1028            * (ascending or descending sequence).
 1029            */
 1030           int[] run = new int[MAX_RUN_COUNT + 1];
 1031           int count = 0; run[0] = left;
 1032   
 1033           // Check if the array is nearly sorted
 1034           for (int k = left; k < right; run[count] = k) {
 1035               if (a[k] < a[k + 1]) { // ascending
 1036                   while (++k <= right && a[k - 1] <= a[k]);
 1037               } else if (a[k] > a[k + 1]) { // descending
 1038                   while (++k <= right && a[k - 1] >= a[k]);
 1039                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
 1040                       short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
 1041                   }
 1042               } else { // equal
 1043                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
 1044                       if (--m == 0) {
 1045                           sort(a, left, right, true);
 1046                           return;
 1047                       }
 1048                   }
 1049               }
 1050   
 1051               /*
 1052                * The array is not highly structured,
 1053                * use Quicksort instead of merge sort.
 1054                */
 1055               if (++count == MAX_RUN_COUNT) {
 1056                   sort(a, left, right, true);
 1057                   return;
 1058               }
 1059           }
 1060   
 1061           // Check special cases
 1062           if (run[count] == right++) { // The last run contains one element
 1063               run[++count] = right;
 1064           } else if (count == 1) { // The array is already sorted
 1065               return;
 1066           }
 1067   
 1068           /*
 1069            * Create temporary array, which is used for merging.
 1070            * Implementation note: variable "right" is increased by 1.
 1071            */
 1072           short[] b; byte odd = 0;
 1073           for (int n = 1; (n <<= 1) < count; odd ^= 1);
 1074   
 1075           if (odd == 0) {
 1076               b = a; a = new short[b.length];
 1077               for (int i = left - 1; ++i < right; a[i] = b[i]);
 1078           } else {
 1079               b = new short[a.length];
 1080           }
 1081   
 1082           // Merging
 1083           for (int last; count > 1; count = last) {
 1084               for (int k = (last = 0) + 2; k <= count; k += 2) {
 1085                   int hi = run[k], mi = run[k - 1];
 1086                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
 1087                       if (q >= hi || p < mi && a[p] <= a[q]) {
 1088                           b[i] = a[p++];
 1089                       } else {
 1090                           b[i] = a[q++];
 1091                       }
 1092                   }
 1093                   run[++last] = hi;
 1094               }
 1095               if ((count & 1) != 0) {
 1096                   for (int i = right, lo = run[count - 1]; --i >= lo;
 1097                       b[i] = a[i]
 1098                   );
 1099                   run[++last] = right;
 1100               }
 1101               short[] t = a; a = b; b = t;
 1102           }
 1103       }
 1104   
 1105       /**
 1106        * Sorts the specified range of the array by Dual-Pivot Quicksort.
 1107        *
 1108        * @param a the array to be sorted
 1109        * @param left the index of the first element, inclusive, to be sorted
 1110        * @param right the index of the last element, inclusive, to be sorted
 1111        * @param leftmost indicates if this part is the leftmost in the range
 1112        */
 1113       private static void sort(short[] a, int left, int right, boolean leftmost) {
 1114           int length = right - left + 1;
 1115   
 1116           // Use insertion sort on tiny arrays
 1117           if (length < INSERTION_SORT_THRESHOLD) {
 1118               if (leftmost) {
 1119                   /*
 1120                    * Traditional (without sentinel) insertion sort,
 1121                    * optimized for server VM, is used in case of
 1122                    * the leftmost part.
 1123                    */
 1124                   for (int i = left, j = i; i < right; j = ++i) {
 1125                       short ai = a[i + 1];
 1126                       while (ai < a[j]) {
 1127                           a[j + 1] = a[j];
 1128                           if (j-- == left) {
 1129                               break;
 1130                           }
 1131                       }
 1132                       a[j + 1] = ai;
 1133                   }
 1134               } else {
 1135                   /*
 1136                    * Skip the longest ascending sequence.
 1137                    */
 1138                   do {
 1139                       if (left >= right) {
 1140                           return;
 1141                       }
 1142                   } while (a[++left] >= a[left - 1]);
 1143   
 1144                   /*
 1145                    * Every element from adjoining part plays the role
 1146                    * of sentinel, therefore this allows us to avoid the
 1147                    * left range check on each iteration. Moreover, we use
 1148                    * the more optimized algorithm, so called pair insertion
 1149                    * sort, which is faster (in the context of Quicksort)
 1150                    * than traditional implementation of insertion sort.
 1151                    */
 1152                   for (int k = left; ++left <= right; k = ++left) {
 1153                       short a1 = a[k], a2 = a[left];
 1154   
 1155                       if (a1 < a2) {
 1156                           a2 = a1; a1 = a[left];
 1157                       }
 1158                       while (a1 < a[--k]) {
 1159                           a[k + 2] = a[k];
 1160                       }
 1161                       a[++k + 1] = a1;
 1162   
 1163                       while (a2 < a[--k]) {
 1164                           a[k + 1] = a[k];
 1165                       }
 1166                       a[k + 1] = a2;
 1167                   }
 1168                   short last = a[right];
 1169   
 1170                   while (last < a[--right]) {
 1171                       a[right + 1] = a[right];
 1172                   }
 1173                   a[right + 1] = last;
 1174               }
 1175               return;
 1176           }
 1177   
 1178           // Inexpensive approximation of length / 7
 1179           int seventh = (length >> 3) + (length >> 6) + 1;
 1180   
 1181           /*
 1182            * Sort five evenly spaced elements around (and including) the
 1183            * center element in the range. These elements will be used for
 1184            * pivot selection as described below. The choice for spacing
 1185            * these elements was empirically determined to work well on
 1186            * a wide variety of inputs.
 1187            */
 1188           int e3 = (left + right) >>> 1; // The midpoint
 1189           int e2 = e3 - seventh;
 1190           int e1 = e2 - seventh;
 1191           int e4 = e3 + seventh;
 1192           int e5 = e4 + seventh;
 1193   
 1194           // Sort these elements using insertion sort
 1195           if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 1196   
 1197           if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
 1198               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1199           }
 1200           if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
 1201               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 1202                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1203               }
 1204           }
 1205           if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
 1206               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
 1207                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 1208                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1209                   }
 1210               }
 1211           }
 1212   
 1213           // Pointers
 1214           int less  = left;  // The index of the first element of center part
 1215           int great = right; // The index before the first element of right part
 1216   
 1217           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
 1218               /*
 1219                * Use the second and fourth of the five sorted elements as pivots.
 1220                * These values are inexpensive approximations of the first and
 1221                * second terciles of the array. Note that pivot1 <= pivot2.
 1222                */
 1223               short pivot1 = a[e2];
 1224               short pivot2 = a[e4];
 1225   
 1226               /*
 1227                * The first and the last elements to be sorted are moved to the
 1228                * locations formerly occupied by the pivots. When partitioning
 1229                * is complete, the pivots are swapped back into their final
 1230                * positions, and excluded from subsequent sorting.
 1231                */
 1232               a[e2] = a[left];
 1233               a[e4] = a[right];
 1234   
 1235               /*
 1236                * Skip elements, which are less or greater than pivot values.
 1237                */
 1238               while (a[++less] < pivot1);
 1239               while (a[--great] > pivot2);
 1240   
 1241               /*
 1242                * Partitioning:
 1243                *
 1244                *   left part           center part                   right part
 1245                * +--------------------------------------------------------------+
 1246                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 1247                * +--------------------------------------------------------------+
 1248                *               ^                          ^       ^
 1249                *               |                          |       |
 1250                *              less                        k     great
 1251                *
 1252                * Invariants:
 1253                *
 1254                *              all in (left, less)   < pivot1
 1255                *    pivot1 <= all in [less, k)     <= pivot2
 1256                *              all in (great, right) > pivot2
 1257                *
 1258                * Pointer k is the first index of ?-part.
 1259                */
 1260               outer:
 1261               for (int k = less - 1; ++k <= great; ) {
 1262                   short ak = a[k];
 1263                   if (ak < pivot1) { // Move a[k] to left part
 1264                       a[k] = a[less];
 1265                       /*
 1266                        * Here and below we use "a[i] = b; i++;" instead
 1267                        * of "a[i++] = b;" due to performance issue.
 1268                        */
 1269                       a[less] = ak;
 1270                       ++less;
 1271                   } else if (ak > pivot2) { // Move a[k] to right part
 1272                       while (a[great] > pivot2) {
 1273                           if (great-- == k) {
 1274                               break outer;
 1275                           }
 1276                       }
 1277                       if (a[great] < pivot1) { // a[great] <= pivot2
 1278                           a[k] = a[less];
 1279                           a[less] = a[great];
 1280                           ++less;
 1281                       } else { // pivot1 <= a[great] <= pivot2
 1282                           a[k] = a[great];
 1283                       }
 1284                       /*
 1285                        * Here and below we use "a[i] = b; i--;" instead
 1286                        * of "a[i--] = b;" due to performance issue.
 1287                        */
 1288                       a[great] = ak;
 1289                       --great;
 1290                   }
 1291               }
 1292   
 1293               // Swap pivots into their final positions
 1294               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 1295               a[right] = a[great + 1]; a[great + 1] = pivot2;
 1296   
 1297               // Sort left and right parts recursively, excluding known pivots
 1298               sort(a, left, less - 2, leftmost);
 1299               sort(a, great + 2, right, false);
 1300   
 1301               /*
 1302                * If center part is too large (comprises > 4/7 of the array),
 1303                * swap internal pivot values to ends.
 1304                */
 1305               if (less < e1 && e5 < great) {
 1306                   /*
 1307                    * Skip elements, which are equal to pivot values.
 1308                    */
 1309                   while (a[less] == pivot1) {
 1310                       ++less;
 1311                   }
 1312   
 1313                   while (a[great] == pivot2) {
 1314                       --great;
 1315                   }
 1316   
 1317                   /*
 1318                    * Partitioning:
 1319                    *
 1320                    *   left part         center part                  right part
 1321                    * +----------------------------------------------------------+
 1322                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
 1323                    * +----------------------------------------------------------+
 1324                    *              ^                        ^       ^
 1325                    *              |                        |       |
 1326                    *             less                      k     great
 1327                    *
 1328                    * Invariants:
 1329                    *
 1330                    *              all in (*,  less) == pivot1
 1331                    *     pivot1 < all in [less,  k)  < pivot2
 1332                    *              all in (great, *) == pivot2
 1333                    *
 1334                    * Pointer k is the first index of ?-part.
 1335                    */
 1336                   outer:
 1337                   for (int k = less - 1; ++k <= great; ) {
 1338                       short ak = a[k];
 1339                       if (ak == pivot1) { // Move a[k] to left part
 1340                           a[k] = a[less];
 1341                           a[less] = ak;
 1342                           ++less;
 1343                       } else if (ak == pivot2) { // Move a[k] to right part
 1344                           while (a[great] == pivot2) {
 1345                               if (great-- == k) {
 1346                                   break outer;
 1347                               }
 1348                           }
 1349                           if (a[great] == pivot1) { // a[great] < pivot2
 1350                               a[k] = a[less];
 1351                               /*
 1352                                * Even though a[great] equals to pivot1, the
 1353                                * assignment a[less] = pivot1 may be incorrect,
 1354                                * if a[great] and pivot1 are floating-point zeros
 1355                                * of different signs. Therefore in float and
 1356                                * double sorting methods we have to use more
 1357                                * accurate assignment a[less] = a[great].
 1358                                */
 1359                               a[less] = pivot1;
 1360                               ++less;
 1361                           } else { // pivot1 < a[great] < pivot2
 1362                               a[k] = a[great];
 1363                           }
 1364                           a[great] = ak;
 1365                           --great;
 1366                       }
 1367                   }
 1368               }
 1369   
 1370               // Sort center part recursively
 1371               sort(a, less, great, false);
 1372   
 1373           } else { // Partitioning with one pivot
 1374               /*
 1375                * Use the third of the five sorted elements as pivot.
 1376                * This value is inexpensive approximation of the median.
 1377                */
 1378               short pivot = a[e3];
 1379   
 1380               /*
 1381                * Partitioning degenerates to the traditional 3-way
 1382                * (or "Dutch National Flag") schema:
 1383                *
 1384                *   left part    center part              right part
 1385                * +-------------------------------------------------+
 1386                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
 1387                * +-------------------------------------------------+
 1388                *              ^              ^        ^
 1389                *              |              |        |
 1390                *             less            k      great
 1391                *
 1392                * Invariants:
 1393                *
 1394                *   all in (left, less)   < pivot
 1395                *   all in [less, k)     == pivot
 1396                *   all in (great, right) > pivot
 1397                *
 1398                * Pointer k is the first index of ?-part.
 1399                */
 1400               for (int k = less; k <= great; ++k) {
 1401                   if (a[k] == pivot) {
 1402                       continue;
 1403                   }
 1404                   short ak = a[k];
 1405                   if (ak < pivot) { // Move a[k] to left part
 1406                       a[k] = a[less];
 1407                       a[less] = ak;
 1408                       ++less;
 1409                   } else { // a[k] > pivot - Move a[k] to right part
 1410                       while (a[great] > pivot) {
 1411                           --great;
 1412                       }
 1413                       if (a[great] < pivot) { // a[great] <= pivot
 1414                           a[k] = a[less];
 1415                           a[less] = a[great];
 1416                           ++less;
 1417                       } else { // a[great] == pivot
 1418                           /*
 1419                            * Even though a[great] equals to pivot, the
 1420                            * assignment a[k] = pivot may be incorrect,
 1421                            * if a[great] and pivot are floating-point
 1422                            * zeros of different signs. Therefore in float
 1423                            * and double sorting methods we have to use
 1424                            * more accurate assignment a[k] = a[great].
 1425                            */
 1426                           a[k] = pivot;
 1427                       }
 1428                       a[great] = ak;
 1429                       --great;
 1430                   }
 1431               }
 1432   
 1433               /*
 1434                * Sort left and right parts recursively.
 1435                * All elements from center part are equal
 1436                * and, therefore, already sorted.
 1437                */
 1438               sort(a, left, less - 1, leftmost);
 1439               sort(a, great + 1, right, false);
 1440           }
 1441       }
 1442   
 1443       /**
 1444        * Sorts the specified array.
 1445        *
 1446        * @param a the array to be sorted
 1447        */
 1448       public static void sort(char[] a) {
 1449           sort(a, 0, a.length - 1);
 1450       }
 1451   
 1452       /**
 1453        * Sorts the specified range of the array.
 1454        *
 1455        * @param a the array to be sorted
 1456        * @param left the index of the first element, inclusive, to be sorted
 1457        * @param right the index of the last element, inclusive, to be sorted
 1458        */
 1459       public static void sort(char[] a, int left, int right) {
 1460           // Use counting sort on large arrays
 1461           if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
 1462               int[] count = new int[NUM_CHAR_VALUES];
 1463   
 1464               for (int i = left - 1; ++i <= right;
 1465                   count[a[i]]++
 1466               );
 1467               for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
 1468                   while (count[--i] == 0);
 1469                   char value = (char) i;
 1470                   int s = count[i];
 1471   
 1472                   do {
 1473                       a[--k] = value;
 1474                   } while (--s > 0);
 1475               }
 1476           } else { // Use Dual-Pivot Quicksort on small arrays
 1477               doSort(a, left, right);
 1478           }
 1479       }
 1480   
 1481       /** The number of distinct char values. */
 1482       private static final int NUM_CHAR_VALUES = 1 << 16;
 1483   
 1484       /**
 1485        * Sorts the specified range of the array.
 1486        *
 1487        * @param a the array to be sorted
 1488        * @param left the index of the first element, inclusive, to be sorted
 1489        * @param right the index of the last element, inclusive, to be sorted
 1490        */
 1491       private static void doSort(char[] a, int left, int right) {
 1492           // Use Quicksort on small arrays
 1493           if (right - left < QUICKSORT_THRESHOLD) {
 1494               sort(a, left, right, true);
 1495               return;
 1496           }
 1497   
 1498           /*
 1499            * Index run[i] is the start of i-th run
 1500            * (ascending or descending sequence).
 1501            */
 1502           int[] run = new int[MAX_RUN_COUNT + 1];
 1503           int count = 0; run[0] = left;
 1504   
 1505           // Check if the array is nearly sorted
 1506           for (int k = left; k < right; run[count] = k) {
 1507               if (a[k] < a[k + 1]) { // ascending
 1508                   while (++k <= right && a[k - 1] <= a[k]);
 1509               } else if (a[k] > a[k + 1]) { // descending
 1510                   while (++k <= right && a[k - 1] >= a[k]);
 1511                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
 1512                       char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
 1513                   }
 1514               } else { // equal
 1515                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
 1516                       if (--m == 0) {
 1517                           sort(a, left, right, true);
 1518                           return;
 1519                       }
 1520                   }
 1521               }
 1522   
 1523               /*
 1524                * The array is not highly structured,
 1525                * use Quicksort instead of merge sort.
 1526                */
 1527               if (++count == MAX_RUN_COUNT) {
 1528                   sort(a, left, right, true);
 1529                   return;
 1530               }
 1531           }
 1532   
 1533           // Check special cases
 1534           if (run[count] == right++) { // The last run contains one element
 1535               run[++count] = right;
 1536           } else if (count == 1) { // The array is already sorted
 1537               return;
 1538           }
 1539   
 1540           /*
 1541            * Create temporary array, which is used for merging.
 1542            * Implementation note: variable "right" is increased by 1.
 1543            */
 1544           char[] b; byte odd = 0;
 1545           for (int n = 1; (n <<= 1) < count; odd ^= 1);
 1546   
 1547           if (odd == 0) {
 1548               b = a; a = new char[b.length];
 1549               for (int i = left - 1; ++i < right; a[i] = b[i]);
 1550           } else {
 1551               b = new char[a.length];
 1552           }
 1553   
 1554           // Merging
 1555           for (int last; count > 1; count = last) {
 1556               for (int k = (last = 0) + 2; k <= count; k += 2) {
 1557                   int hi = run[k], mi = run[k - 1];
 1558                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
 1559                       if (q >= hi || p < mi && a[p] <= a[q]) {
 1560                           b[i] = a[p++];
 1561                       } else {
 1562                           b[i] = a[q++];
 1563                       }
 1564                   }
 1565                   run[++last] = hi;
 1566               }
 1567               if ((count & 1) != 0) {
 1568                   for (int i = right, lo = run[count - 1]; --i >= lo;
 1569                       b[i] = a[i]
 1570                   );
 1571                   run[++last] = right;
 1572               }
 1573               char[] t = a; a = b; b = t;
 1574           }
 1575       }
 1576   
 1577       /**
 1578        * Sorts the specified range of the array by Dual-Pivot Quicksort.
 1579        *
 1580        * @param a the array to be sorted
 1581        * @param left the index of the first element, inclusive, to be sorted
 1582        * @param right the index of the last element, inclusive, to be sorted
 1583        * @param leftmost indicates if this part is the leftmost in the range
 1584        */
 1585       private static void sort(char[] a, int left, int right, boolean leftmost) {
 1586           int length = right - left + 1;
 1587   
 1588           // Use insertion sort on tiny arrays
 1589           if (length < INSERTION_SORT_THRESHOLD) {
 1590               if (leftmost) {
 1591                   /*
 1592                    * Traditional (without sentinel) insertion sort,
 1593                    * optimized for server VM, is used in case of
 1594                    * the leftmost part.
 1595                    */
 1596                   for (int i = left, j = i; i < right; j = ++i) {
 1597                       char ai = a[i + 1];
 1598                       while (ai < a[j]) {
 1599                           a[j + 1] = a[j];
 1600                           if (j-- == left) {
 1601                               break;
 1602                           }
 1603                       }
 1604                       a[j + 1] = ai;
 1605                   }
 1606               } else {
 1607                   /*
 1608                    * Skip the longest ascending sequence.
 1609                    */
 1610                   do {
 1611                       if (left >= right) {
 1612                           return;
 1613                       }
 1614                   } while (a[++left] >= a[left - 1]);
 1615   
 1616                   /*
 1617                    * Every element from adjoining part plays the role
 1618                    * of sentinel, therefore this allows us to avoid the
 1619                    * left range check on each iteration. Moreover, we use
 1620                    * the more optimized algorithm, so called pair insertion
 1621                    * sort, which is faster (in the context of Quicksort)
 1622                    * than traditional implementation of insertion sort.
 1623                    */
 1624                   for (int k = left; ++left <= right; k = ++left) {
 1625                       char a1 = a[k], a2 = a[left];
 1626   
 1627                       if (a1 < a2) {
 1628                           a2 = a1; a1 = a[left];
 1629                       }
 1630                       while (a1 < a[--k]) {
 1631                           a[k + 2] = a[k];
 1632                       }
 1633                       a[++k + 1] = a1;
 1634   
 1635                       while (a2 < a[--k]) {
 1636                           a[k + 1] = a[k];
 1637                       }
 1638                       a[k + 1] = a2;
 1639                   }
 1640                   char last = a[right];
 1641   
 1642                   while (last < a[--right]) {
 1643                       a[right + 1] = a[right];
 1644                   }
 1645                   a[right + 1] = last;
 1646               }
 1647               return;
 1648           }
 1649   
 1650           // Inexpensive approximation of length / 7
 1651           int seventh = (length >> 3) + (length >> 6) + 1;
 1652   
 1653           /*
 1654            * Sort five evenly spaced elements around (and including) the
 1655            * center element in the range. These elements will be used for
 1656            * pivot selection as described below. The choice for spacing
 1657            * these elements was empirically determined to work well on
 1658            * a wide variety of inputs.
 1659            */
 1660           int e3 = (left + right) >>> 1; // The midpoint
 1661           int e2 = e3 - seventh;
 1662           int e1 = e2 - seventh;
 1663           int e4 = e3 + seventh;
 1664           int e5 = e4 + seventh;
 1665   
 1666           // Sort these elements using insertion sort
 1667           if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 1668   
 1669           if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
 1670               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1671           }
 1672           if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
 1673               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 1674                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1675               }
 1676           }
 1677           if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
 1678               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
 1679                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 1680                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 1681                   }
 1682               }
 1683           }
 1684   
 1685           // Pointers
 1686           int less  = left;  // The index of the first element of center part
 1687           int great = right; // The index before the first element of right part
 1688   
 1689           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
 1690               /*
 1691                * Use the second and fourth of the five sorted elements as pivots.
 1692                * These values are inexpensive approximations of the first and
 1693                * second terciles of the array. Note that pivot1 <= pivot2.
 1694                */
 1695               char pivot1 = a[e2];
 1696               char pivot2 = a[e4];
 1697   
 1698               /*
 1699                * The first and the last elements to be sorted are moved to the
 1700                * locations formerly occupied by the pivots. When partitioning
 1701                * is complete, the pivots are swapped back into their final
 1702                * positions, and excluded from subsequent sorting.
 1703                */
 1704               a[e2] = a[left];
 1705               a[e4] = a[right];
 1706   
 1707               /*
 1708                * Skip elements, which are less or greater than pivot values.
 1709                */
 1710               while (a[++less] < pivot1);
 1711               while (a[--great] > pivot2);
 1712   
 1713               /*
 1714                * Partitioning:
 1715                *
 1716                *   left part           center part                   right part
 1717                * +--------------------------------------------------------------+
 1718                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 1719                * +--------------------------------------------------------------+
 1720                *               ^                          ^       ^
 1721                *               |                          |       |
 1722                *              less                        k     great
 1723                *
 1724                * Invariants:
 1725                *
 1726                *              all in (left, less)   < pivot1
 1727                *    pivot1 <= all in [less, k)     <= pivot2
 1728                *              all in (great, right) > pivot2
 1729                *
 1730                * Pointer k is the first index of ?-part.
 1731                */
 1732               outer:
 1733               for (int k = less - 1; ++k <= great; ) {
 1734                   char ak = a[k];
 1735                   if (ak < pivot1) { // Move a[k] to left part
 1736                       a[k] = a[less];
 1737                       /*
 1738                        * Here and below we use "a[i] = b; i++;" instead
 1739                        * of "a[i++] = b;" due to performance issue.
 1740                        */
 1741                       a[less] = ak;
 1742                       ++less;
 1743                   } else if (ak > pivot2) { // Move a[k] to right part
 1744                       while (a[great] > pivot2) {
 1745                           if (great-- == k) {
 1746                               break outer;
 1747                           }
 1748                       }
 1749                       if (a[great] < pivot1) { // a[great] <= pivot2
 1750                           a[k] = a[less];
 1751                           a[less] = a[great];
 1752                           ++less;
 1753                       } else { // pivot1 <= a[great] <= pivot2
 1754                           a[k] = a[great];
 1755                       }
 1756                       /*
 1757                        * Here and below we use "a[i] = b; i--;" instead
 1758                        * of "a[i--] = b;" due to performance issue.
 1759                        */
 1760                       a[great] = ak;
 1761                       --great;
 1762                   }
 1763               }
 1764   
 1765               // Swap pivots into their final positions
 1766               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 1767               a[right] = a[great + 1]; a[great + 1] = pivot2;
 1768   
 1769               // Sort left and right parts recursively, excluding known pivots
 1770               sort(a, left, less - 2, leftmost);
 1771               sort(a, great + 2, right, false);
 1772   
 1773               /*
 1774                * If center part is too large (comprises > 4/7 of the array),
 1775                * swap internal pivot values to ends.
 1776                */
 1777               if (less < e1 && e5 < great) {
 1778                   /*
 1779                    * Skip elements, which are equal to pivot values.
 1780                    */
 1781                   while (a[less] == pivot1) {
 1782                       ++less;
 1783                   }
 1784   
 1785                   while (a[great] == pivot2) {
 1786                       --great;
 1787                   }
 1788   
 1789                   /*
 1790                    * Partitioning:
 1791                    *
 1792                    *   left part         center part                  right part
 1793                    * +----------------------------------------------------------+
 1794                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
 1795                    * +----------------------------------------------------------+
 1796                    *              ^                        ^       ^
 1797                    *              |                        |       |
 1798                    *             less                      k     great
 1799                    *
 1800                    * Invariants:
 1801                    *
 1802                    *              all in (*,  less) == pivot1
 1803                    *     pivot1 < all in [less,  k)  < pivot2
 1804                    *              all in (great, *) == pivot2
 1805                    *
 1806                    * Pointer k is the first index of ?-part.
 1807                    */
 1808                   outer:
 1809                   for (int k = less - 1; ++k <= great; ) {
 1810                       char ak = a[k];
 1811                       if (ak == pivot1) { // Move a[k] to left part
 1812                           a[k] = a[less];
 1813                           a[less] = ak;
 1814                           ++less;
 1815                       } else if (ak == pivot2) { // Move a[k] to right part
 1816                           while (a[great] == pivot2) {
 1817                               if (great-- == k) {
 1818                                   break outer;
 1819                               }
 1820                           }
 1821                           if (a[great] == pivot1) { // a[great] < pivot2
 1822                               a[k] = a[less];
 1823                               /*
 1824                                * Even though a[great] equals to pivot1, the
 1825                                * assignment a[less] = pivot1 may be incorrect,
 1826                                * if a[great] and pivot1 are floating-point zeros
 1827                                * of different signs. Therefore in float and
 1828                                * double sorting methods we have to use more
 1829                                * accurate assignment a[less] = a[great].
 1830                                */
 1831                               a[less] = pivot1;
 1832                               ++less;
 1833                           } else { // pivot1 < a[great] < pivot2
 1834                               a[k] = a[great];
 1835                           }
 1836                           a[great] = ak;
 1837                           --great;
 1838                       }
 1839                   }
 1840               }
 1841   
 1842               // Sort center part recursively
 1843               sort(a, less, great, false);
 1844   
 1845           } else { // Partitioning with one pivot
 1846               /*
 1847                * Use the third of the five sorted elements as pivot.
 1848                * This value is inexpensive approximation of the median.
 1849                */
 1850               char pivot = a[e3];
 1851   
 1852               /*
 1853                * Partitioning degenerates to the traditional 3-way
 1854                * (or "Dutch National Flag") schema:
 1855                *
 1856                *   left part    center part              right part
 1857                * +-------------------------------------------------+
 1858                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
 1859                * +-------------------------------------------------+
 1860                *              ^              ^        ^
 1861                *              |              |        |
 1862                *             less            k      great
 1863                *
 1864                * Invariants:
 1865                *
 1866                *   all in (left, less)   < pivot
 1867                *   all in [less, k)     == pivot
 1868                *   all in (great, right) > pivot
 1869                *
 1870                * Pointer k is the first index of ?-part.
 1871                */
 1872               for (int k = less; k <= great; ++k) {
 1873                   if (a[k] == pivot) {
 1874                       continue;
 1875                   }
 1876                   char ak = a[k];
 1877                   if (ak < pivot) { // Move a[k] to left part
 1878                       a[k] = a[less];
 1879                       a[less] = ak;
 1880                       ++less;
 1881                   } else { // a[k] > pivot - Move a[k] to right part
 1882                       while (a[great] > pivot) {
 1883                           --great;
 1884                       }
 1885                       if (a[great] < pivot) { // a[great] <= pivot
 1886                           a[k] = a[less];
 1887                           a[less] = a[great];
 1888                           ++less;
 1889                       } else { // a[great] == pivot
 1890                           /*
 1891                            * Even though a[great] equals to pivot, the
 1892                            * assignment a[k] = pivot may be incorrect,
 1893                            * if a[great] and pivot are floating-point
 1894                            * zeros of different signs. Therefore in float
 1895                            * and double sorting methods we have to use
 1896                            * more accurate assignment a[k] = a[great].
 1897                            */
 1898                           a[k] = pivot;
 1899                       }
 1900                       a[great] = ak;
 1901                       --great;
 1902                   }
 1903               }
 1904   
 1905               /*
 1906                * Sort left and right parts recursively.
 1907                * All elements from center part are equal
 1908                * and, therefore, already sorted.
 1909                */
 1910               sort(a, left, less - 1, leftmost);
 1911               sort(a, great + 1, right, false);
 1912           }
 1913       }
 1914   
 1915       /** The number of distinct byte values. */
 1916       private static final int NUM_BYTE_VALUES = 1 << 8;
 1917   
 1918       /**
 1919        * Sorts the specified array.
 1920        *
 1921        * @param a the array to be sorted
 1922        */
 1923       public static void sort(byte[] a) {
 1924           sort(a, 0, a.length - 1);
 1925       }
 1926   
 1927       /**
 1928        * Sorts the specified range of the array.
 1929        *
 1930        * @param a the array to be sorted
 1931        * @param left the index of the first element, inclusive, to be sorted
 1932        * @param right the index of the last element, inclusive, to be sorted
 1933        */
 1934       public static void sort(byte[] a, int left, int right) {
 1935           // Use counting sort on large arrays
 1936           if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
 1937               int[] count = new int[NUM_BYTE_VALUES];
 1938   
 1939               for (int i = left - 1; ++i <= right;
 1940                   count[a[i] - Byte.MIN_VALUE]++
 1941               );
 1942               for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
 1943                   while (count[--i] == 0);
 1944                   byte value = (byte) (i + Byte.MIN_VALUE);
 1945                   int s = count[i];
 1946   
 1947                   do {
 1948                       a[--k] = value;
 1949                   } while (--s > 0);
 1950               }
 1951           } else { // Use insertion sort on small arrays
 1952               for (int i = left, j = i; i < right; j = ++i) {
 1953                   byte ai = a[i + 1];
 1954                   while (ai < a[j]) {
 1955                       a[j + 1] = a[j];
 1956                       if (j-- == left) {
 1957                           break;
 1958                       }
 1959                   }
 1960                   a[j + 1] = ai;
 1961               }
 1962           }
 1963       }
 1964   
 1965       /**
 1966        * Sorts the specified array.
 1967        *
 1968        * @param a the array to be sorted
 1969        */
 1970       public static void sort(float[] a) {
 1971           sort(a, 0, a.length - 1);
 1972       }
 1973   
 1974       /**
 1975        * Sorts the specified range of the array.
 1976        *
 1977        * @param a the array to be sorted
 1978        * @param left the index of the first element, inclusive, to be sorted
 1979        * @param right the index of the last element, inclusive, to be sorted
 1980        */
 1981       public static void sort(float[] a, int left, int right) {
 1982           /*
 1983            * Phase 1: Move NaNs to the end of the array.
 1984            */
 1985           while (left <= right && Float.isNaN(a[right])) {
 1986               --right;
 1987           }
 1988           for (int k = right; --k >= left; ) {
 1989               float ak = a[k];
 1990               if (ak != ak) { // a[k] is NaN
 1991                   a[k] = a[right];
 1992                   a[right] = ak;
 1993                   --right;
 1994               }
 1995           }
 1996   
 1997           /*
 1998            * Phase 2: Sort everything except NaNs (which are already in place).
 1999            */
 2000           doSort(a, left, right);
 2001   
 2002           /*
 2003            * Phase 3: Place negative zeros before positive zeros.
 2004            */
 2005           int hi = right;
 2006   
 2007           /*
 2008            * Find the first zero, or first positive, or last negative element.
 2009            */
 2010           while (left < hi) {
 2011               int middle = (left + hi) >>> 1;
 2012               float middleValue = a[middle];
 2013   
 2014               if (middleValue < 0.0f) {
 2015                   left = middle + 1;
 2016               } else {
 2017                   hi = middle;
 2018               }
 2019           }
 2020   
 2021           /*
 2022            * Skip the last negative value (if any) or all leading negative zeros.
 2023            */
 2024           while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
 2025               ++left;
 2026           }
 2027   
 2028           /*
 2029            * Move negative zeros to the beginning of the sub-range.
 2030            *
 2031            * Partitioning:
 2032            *
 2033            * +----------------------------------------------------+
 2034            * |   < 0.0   |   -0.0   |   0.0   |   ?  ( >= 0.0 )   |
 2035            * +----------------------------------------------------+
 2036            *              ^          ^         ^
 2037            *              |          |         |
 2038            *             left        p         k
 2039            *
 2040            * Invariants:
 2041            *
 2042            *   all in (*,  left)  <  0.0
 2043            *   all in [left,  p) == -0.0
 2044            *   all in [p,     k) ==  0.0
 2045            *   all in [k, right] >=  0.0
 2046            *
 2047            * Pointer k is the first index of ?-part.
 2048            */
 2049           for (int k = left, p = left - 1; ++k <= right; ) {
 2050               float ak = a[k];
 2051               if (ak != 0.0f) {
 2052                   break;
 2053               }
 2054               if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
 2055                   a[k] = 0.0f;
 2056                   a[++p] = -0.0f;
 2057               }
 2058           }
 2059       }
 2060   
 2061       /**
 2062        * Sorts the specified range of the array.
 2063        *
 2064        * @param a the array to be sorted
 2065        * @param left the index of the first element, inclusive, to be sorted
 2066        * @param right the index of the last element, inclusive, to be sorted
 2067        */
 2068       private static void doSort(float[] a, int left, int right) {
 2069           // Use Quicksort on small arrays
 2070           if (right - left < QUICKSORT_THRESHOLD) {
 2071               sort(a, left, right, true);
 2072               return;
 2073           }
 2074   
 2075           /*
 2076            * Index run[i] is the start of i-th run
 2077            * (ascending or descending sequence).
 2078            */
 2079           int[] run = new int[MAX_RUN_COUNT + 1];
 2080           int count = 0; run[0] = left;
 2081   
 2082           // Check if the array is nearly sorted
 2083           for (int k = left; k < right; run[count] = k) {
 2084               if (a[k] < a[k + 1]) { // ascending
 2085                   while (++k <= right && a[k - 1] <= a[k]);
 2086               } else if (a[k] > a[k + 1]) { // descending
 2087                   while (++k <= right && a[k - 1] >= a[k]);
 2088                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
 2089                       float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
 2090                   }
 2091               } else { // equal
 2092                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
 2093                       if (--m == 0) {
 2094                           sort(a, left, right, true);
 2095                           return;
 2096                       }
 2097                   }
 2098               }
 2099   
 2100               /*
 2101                * The array is not highly structured,
 2102                * use Quicksort instead of merge sort.
 2103                */
 2104               if (++count == MAX_RUN_COUNT) {
 2105                   sort(a, left, right, true);
 2106                   return;
 2107               }
 2108           }
 2109   
 2110           // Check special cases
 2111           if (run[count] == right++) { // The last run contains one element
 2112               run[++count] = right;
 2113           } else if (count == 1) { // The array is already sorted
 2114               return;
 2115           }
 2116   
 2117           /*
 2118            * Create temporary array, which is used for merging.
 2119            * Implementation note: variable "right" is increased by 1.
 2120            */
 2121           float[] b; byte odd = 0;
 2122           for (int n = 1; (n <<= 1) < count; odd ^= 1);
 2123   
 2124           if (odd == 0) {
 2125               b = a; a = new float[b.length];
 2126               for (int i = left - 1; ++i < right; a[i] = b[i]);
 2127           } else {
 2128               b = new float[a.length];
 2129           }
 2130   
 2131           // Merging
 2132           for (int last; count > 1; count = last) {
 2133               for (int k = (last = 0) + 2; k <= count; k += 2) {
 2134                   int hi = run[k], mi = run[k - 1];
 2135                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
 2136                       if (q >= hi || p < mi && a[p] <= a[q]) {
 2137                           b[i] = a[p++];
 2138                       } else {
 2139                           b[i] = a[q++];
 2140                       }
 2141                   }
 2142                   run[++last] = hi;
 2143               }
 2144               if ((count & 1) != 0) {
 2145                   for (int i = right, lo = run[count - 1]; --i >= lo;
 2146                       b[i] = a[i]
 2147                   );
 2148                   run[++last] = right;
 2149               }
 2150               float[] t = a; a = b; b = t;
 2151           }
 2152       }
 2153   
 2154       /**
 2155        * Sorts the specified range of the array by Dual-Pivot Quicksort.
 2156        *
 2157        * @param a the array to be sorted
 2158        * @param left the index of the first element, inclusive, to be sorted
 2159        * @param right the index of the last element, inclusive, to be sorted
 2160        * @param leftmost indicates if this part is the leftmost in the range
 2161        */
 2162       private static void sort(float[] a, int left, int right, boolean leftmost) {
 2163           int length = right - left + 1;
 2164   
 2165           // Use insertion sort on tiny arrays
 2166           if (length < INSERTION_SORT_THRESHOLD) {
 2167               if (leftmost) {
 2168                   /*
 2169                    * Traditional (without sentinel) insertion sort,
 2170                    * optimized for server VM, is used in case of
 2171                    * the leftmost part.
 2172                    */
 2173                   for (int i = left, j = i; i < right; j = ++i) {
 2174                       float ai = a[i + 1];
 2175                       while (ai < a[j]) {
 2176                           a[j + 1] = a[j];
 2177                           if (j-- == left) {
 2178                               break;
 2179                           }
 2180                       }
 2181                       a[j + 1] = ai;
 2182                   }
 2183               } else {
 2184                   /*
 2185                    * Skip the longest ascending sequence.
 2186                    */
 2187                   do {
 2188                       if (left >= right) {
 2189                           return;
 2190                       }
 2191                   } while (a[++left] >= a[left - 1]);
 2192   
 2193                   /*
 2194                    * Every element from adjoining part plays the role
 2195                    * of sentinel, therefore this allows us to avoid the
 2196                    * left range check on each iteration. Moreover, we use
 2197                    * the more optimized algorithm, so called pair insertion
 2198                    * sort, which is faster (in the context of Quicksort)
 2199                    * than traditional implementation of insertion sort.
 2200                    */
 2201                   for (int k = left; ++left <= right; k = ++left) {
 2202                       float a1 = a[k], a2 = a[left];
 2203   
 2204                       if (a1 < a2) {
 2205                           a2 = a1; a1 = a[left];
 2206                       }
 2207                       while (a1 < a[--k]) {
 2208                           a[k + 2] = a[k];
 2209                       }
 2210                       a[++k + 1] = a1;
 2211   
 2212                       while (a2 < a[--k]) {
 2213                           a[k + 1] = a[k];
 2214                       }
 2215                       a[k + 1] = a2;
 2216                   }
 2217                   float last = a[right];
 2218   
 2219                   while (last < a[--right]) {
 2220                       a[right + 1] = a[right];
 2221                   }
 2222                   a[right + 1] = last;
 2223               }
 2224               return;
 2225           }
 2226   
 2227           // Inexpensive approximation of length / 7
 2228           int seventh = (length >> 3) + (length >> 6) + 1;
 2229   
 2230           /*
 2231            * Sort five evenly spaced elements around (and including) the
 2232            * center element in the range. These elements will be used for
 2233            * pivot selection as described below. The choice for spacing
 2234            * these elements was empirically determined to work well on
 2235            * a wide variety of inputs.
 2236            */
 2237           int e3 = (left + right) >>> 1; // The midpoint
 2238           int e2 = e3 - seventh;
 2239           int e1 = e2 - seventh;
 2240           int e4 = e3 + seventh;
 2241           int e5 = e4 + seventh;
 2242   
 2243           // Sort these elements using insertion sort
 2244           if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 2245   
 2246           if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
 2247               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2248           }
 2249           if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
 2250               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 2251                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2252               }
 2253           }
 2254           if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
 2255               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
 2256                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 2257                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2258                   }
 2259               }
 2260           }
 2261   
 2262           // Pointers
 2263           int less  = left;  // The index of the first element of center part
 2264           int great = right; // The index before the first element of right part
 2265   
 2266           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
 2267               /*
 2268                * Use the second and fourth of the five sorted elements as pivots.
 2269                * These values are inexpensive approximations of the first and
 2270                * second terciles of the array. Note that pivot1 <= pivot2.
 2271                */
 2272               float pivot1 = a[e2];
 2273               float pivot2 = a[e4];
 2274   
 2275               /*
 2276                * The first and the last elements to be sorted are moved to the
 2277                * locations formerly occupied by the pivots. When partitioning
 2278                * is complete, the pivots are swapped back into their final
 2279                * positions, and excluded from subsequent sorting.
 2280                */
 2281               a[e2] = a[left];
 2282               a[e4] = a[right];
 2283   
 2284               /*
 2285                * Skip elements, which are less or greater than pivot values.
 2286                */
 2287               while (a[++less] < pivot1);
 2288               while (a[--great] > pivot2);
 2289   
 2290               /*
 2291                * Partitioning:
 2292                *
 2293                *   left part           center part                   right part
 2294                * +--------------------------------------------------------------+
 2295                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 2296                * +--------------------------------------------------------------+
 2297                *               ^                          ^       ^
 2298                *               |                          |       |
 2299                *              less                        k     great
 2300                *
 2301                * Invariants:
 2302                *
 2303                *              all in (left, less)   < pivot1
 2304                *    pivot1 <= all in [less, k)     <= pivot2
 2305                *              all in (great, right) > pivot2
 2306                *
 2307                * Pointer k is the first index of ?-part.
 2308                */
 2309               outer:
 2310               for (int k = less - 1; ++k <= great; ) {
 2311                   float ak = a[k];
 2312                   if (ak < pivot1) { // Move a[k] to left part
 2313                       a[k] = a[less];
 2314                       /*
 2315                        * Here and below we use "a[i] = b; i++;" instead
 2316                        * of "a[i++] = b;" due to performance issue.
 2317                        */
 2318                       a[less] = ak;
 2319                       ++less;
 2320                   } else if (ak > pivot2) { // Move a[k] to right part
 2321                       while (a[great] > pivot2) {
 2322                           if (great-- == k) {
 2323                               break outer;
 2324                           }
 2325                       }
 2326                       if (a[great] < pivot1) { // a[great] <= pivot2
 2327                           a[k] = a[less];
 2328                           a[less] = a[great];
 2329                           ++less;
 2330                       } else { // pivot1 <= a[great] <= pivot2
 2331                           a[k] = a[great];
 2332                       }
 2333                       /*
 2334                        * Here and below we use "a[i] = b; i--;" instead
 2335                        * of "a[i--] = b;" due to performance issue.
 2336                        */
 2337                       a[great] = ak;
 2338                       --great;
 2339                   }
 2340               }
 2341   
 2342               // Swap pivots into their final positions
 2343               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 2344               a[right] = a[great + 1]; a[great + 1] = pivot2;
 2345   
 2346               // Sort left and right parts recursively, excluding known pivots
 2347               sort(a, left, less - 2, leftmost);
 2348               sort(a, great + 2, right, false);
 2349   
 2350               /*
 2351                * If center part is too large (comprises > 4/7 of the array),
 2352                * swap internal pivot values to ends.
 2353                */
 2354               if (less < e1 && e5 < great) {
 2355                   /*
 2356                    * Skip elements, which are equal to pivot values.
 2357                    */
 2358                   while (a[less] == pivot1) {
 2359                       ++less;
 2360                   }
 2361   
 2362                   while (a[great] == pivot2) {
 2363                       --great;
 2364                   }
 2365   
 2366                   /*
 2367                    * Partitioning:
 2368                    *
 2369                    *   left part         center part                  right part
 2370                    * +----------------------------------------------------------+
 2371                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
 2372                    * +----------------------------------------------------------+
 2373                    *              ^                        ^       ^
 2374                    *              |                        |       |
 2375                    *             less                      k     great
 2376                    *
 2377                    * Invariants:
 2378                    *
 2379                    *              all in (*,  less) == pivot1
 2380                    *     pivot1 < all in [less,  k)  < pivot2
 2381                    *              all in (great, *) == pivot2
 2382                    *
 2383                    * Pointer k is the first index of ?-part.
 2384                    */
 2385                   outer:
 2386                   for (int k = less - 1; ++k <= great; ) {
 2387                       float ak = a[k];
 2388                       if (ak == pivot1) { // Move a[k] to left part
 2389                           a[k] = a[less];
 2390                           a[less] = ak;
 2391                           ++less;
 2392                       } else if (ak == pivot2) { // Move a[k] to right part
 2393                           while (a[great] == pivot2) {
 2394                               if (great-- == k) {
 2395                                   break outer;
 2396                               }
 2397                           }
 2398                           if (a[great] == pivot1) { // a[great] < pivot2
 2399                               a[k] = a[less];
 2400                               /*
 2401                                * Even though a[great] equals to pivot1, the
 2402                                * assignment a[less] = pivot1 may be incorrect,
 2403                                * if a[great] and pivot1 are floating-point zeros
 2404                                * of different signs. Therefore in float and
 2405                                * double sorting methods we have to use more
 2406                                * accurate assignment a[less] = a[great].
 2407                                */
 2408                               a[less] = a[great];
 2409                               ++less;
 2410                           } else { // pivot1 < a[great] < pivot2
 2411                               a[k] = a[great];
 2412                           }
 2413                           a[great] = ak;
 2414                           --great;
 2415                       }
 2416                   }
 2417               }
 2418   
 2419               // Sort center part recursively
 2420               sort(a, less, great, false);
 2421   
 2422           } else { // Partitioning with one pivot
 2423               /*
 2424                * Use the third of the five sorted elements as pivot.
 2425                * This value is inexpensive approximation of the median.
 2426                */
 2427               float pivot = a[e3];
 2428   
 2429               /*
 2430                * Partitioning degenerates to the traditional 3-way
 2431                * (or "Dutch National Flag") schema:
 2432                *
 2433                *   left part    center part              right part
 2434                * +-------------------------------------------------+
 2435                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
 2436                * +-------------------------------------------------+
 2437                *              ^              ^        ^
 2438                *              |              |        |
 2439                *             less            k      great
 2440                *
 2441                * Invariants:
 2442                *
 2443                *   all in (left, less)   < pivot
 2444                *   all in [less, k)     == pivot
 2445                *   all in (great, right) > pivot
 2446                *
 2447                * Pointer k is the first index of ?-part.
 2448                */
 2449               for (int k = less; k <= great; ++k) {
 2450                   if (a[k] == pivot) {
 2451                       continue;
 2452                   }
 2453                   float ak = a[k];
 2454                   if (ak < pivot) { // Move a[k] to left part
 2455                       a[k] = a[less];
 2456                       a[less] = ak;
 2457                       ++less;
 2458                   } else { // a[k] > pivot - Move a[k] to right part
 2459                       while (a[great] > pivot) {
 2460                           --great;
 2461                       }
 2462                       if (a[great] < pivot) { // a[great] <= pivot
 2463                           a[k] = a[less];
 2464                           a[less] = a[great];
 2465                           ++less;
 2466                       } else { // a[great] == pivot
 2467                           /*
 2468                            * Even though a[great] equals to pivot, the
 2469                            * assignment a[k] = pivot may be incorrect,
 2470                            * if a[great] and pivot are floating-point
 2471                            * zeros of different signs. Therefore in float
 2472                            * and double sorting methods we have to use
 2473                            * more accurate assignment a[k] = a[great].
 2474                            */
 2475                           a[k] = a[great];
 2476                       }
 2477                       a[great] = ak;
 2478                       --great;
 2479                   }
 2480               }
 2481   
 2482               /*
 2483                * Sort left and right parts recursively.
 2484                * All elements from center part are equal
 2485                * and, therefore, already sorted.
 2486                */
 2487               sort(a, left, less - 1, leftmost);
 2488               sort(a, great + 1, right, false);
 2489           }
 2490       }
 2491   
 2492       /**
 2493        * Sorts the specified array.
 2494        *
 2495        * @param a the array to be sorted
 2496        */
 2497       public static void sort(double[] a) {
 2498           sort(a, 0, a.length - 1);
 2499       }
 2500   
 2501       /**
 2502        * Sorts the specified range of the array.
 2503        *
 2504        * @param a the array to be sorted
 2505        * @param left the index of the first element, inclusive, to be sorted
 2506        * @param right the index of the last element, inclusive, to be sorted
 2507        */
 2508       public static void sort(double[] a, int left, int right) {
 2509           /*
 2510            * Phase 1: Move NaNs to the end of the array.
 2511            */
 2512           while (left <= right && Double.isNaN(a[right])) {
 2513               --right;
 2514           }
 2515           for (int k = right; --k >= left; ) {
 2516               double ak = a[k];
 2517               if (ak != ak) { // a[k] is NaN
 2518                   a[k] = a[right];
 2519                   a[right] = ak;
 2520                   --right;
 2521               }
 2522           }
 2523   
 2524           /*
 2525            * Phase 2: Sort everything except NaNs (which are already in place).
 2526            */
 2527           doSort(a, left, right);
 2528   
 2529           /*
 2530            * Phase 3: Place negative zeros before positive zeros.
 2531            */
 2532           int hi = right;
 2533   
 2534           /*
 2535            * Find the first zero, or first positive, or last negative element.
 2536            */
 2537           while (left < hi) {
 2538               int middle = (left + hi) >>> 1;
 2539               double middleValue = a[middle];
 2540   
 2541               if (middleValue < 0.0d) {
 2542                   left = middle + 1;
 2543               } else {
 2544                   hi = middle;
 2545               }
 2546           }
 2547   
 2548           /*
 2549            * Skip the last negative value (if any) or all leading negative zeros.
 2550            */
 2551           while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
 2552               ++left;
 2553           }
 2554   
 2555           /*
 2556            * Move negative zeros to the beginning of the sub-range.
 2557            *
 2558            * Partitioning:
 2559            *
 2560            * +----------------------------------------------------+
 2561            * |   < 0.0   |   -0.0   |   0.0   |   ?  ( >= 0.0 )   |
 2562            * +----------------------------------------------------+
 2563            *              ^          ^         ^
 2564            *              |          |         |
 2565            *             left        p         k
 2566            *
 2567            * Invariants:
 2568            *
 2569            *   all in (*,  left)  <  0.0
 2570            *   all in [left,  p) == -0.0
 2571            *   all in [p,     k) ==  0.0
 2572            *   all in [k, right] >=  0.0
 2573            *
 2574            * Pointer k is the first index of ?-part.
 2575            */
 2576           for (int k = left, p = left - 1; ++k <= right; ) {
 2577               double ak = a[k];
 2578               if (ak != 0.0d) {
 2579                   break;
 2580               }
 2581               if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
 2582                   a[k] = 0.0d;
 2583                   a[++p] = -0.0d;
 2584               }
 2585           }
 2586       }
 2587   
 2588       /**
 2589        * Sorts the specified range of the array.
 2590        *
 2591        * @param a the array to be sorted
 2592        * @param left the index of the first element, inclusive, to be sorted
 2593        * @param right the index of the last element, inclusive, to be sorted
 2594        */
 2595       private static void doSort(double[] a, int left, int right) {
 2596           // Use Quicksort on small arrays
 2597           if (right - left < QUICKSORT_THRESHOLD) {
 2598               sort(a, left, right, true);
 2599               return;
 2600           }
 2601   
 2602           /*
 2603            * Index run[i] is the start of i-th run
 2604            * (ascending or descending sequence).
 2605            */
 2606           int[] run = new int[MAX_RUN_COUNT + 1];
 2607           int count = 0; run[0] = left;
 2608   
 2609           // Check if the array is nearly sorted
 2610           for (int k = left; k < right; run[count] = k) {
 2611               if (a[k] < a[k + 1]) { // ascending
 2612                   while (++k <= right && a[k - 1] <= a[k]);
 2613               } else if (a[k] > a[k + 1]) { // descending
 2614                   while (++k <= right && a[k - 1] >= a[k]);
 2615                   for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
 2616                       double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
 2617                   }
 2618               } else { // equal
 2619                   for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
 2620                       if (--m == 0) {
 2621                           sort(a, left, right, true);
 2622                           return;
 2623                       }
 2624                   }
 2625               }
 2626   
 2627               /*
 2628                * The array is not highly structured,
 2629                * use Quicksort instead of merge sort.
 2630                */
 2631               if (++count == MAX_RUN_COUNT) {
 2632                   sort(a, left, right, true);
 2633                   return;
 2634               }
 2635           }
 2636   
 2637           // Check special cases
 2638           if (run[count] == right++) { // The last run contains one element
 2639               run[++count] = right;
 2640           } else if (count == 1) { // The array is already sorted
 2641               return;
 2642           }
 2643   
 2644           /*
 2645            * Create temporary array, which is used for merging.
 2646            * Implementation note: variable "right" is increased by 1.
 2647            */
 2648           double[] b; byte odd = 0;
 2649           for (int n = 1; (n <<= 1) < count; odd ^= 1);
 2650   
 2651           if (odd == 0) {
 2652               b = a; a = new double[b.length];
 2653               for (int i = left - 1; ++i < right; a[i] = b[i]);
 2654           } else {
 2655               b = new double[a.length];
 2656           }
 2657   
 2658           // Merging
 2659           for (int last; count > 1; count = last) {
 2660               for (int k = (last = 0) + 2; k <= count; k += 2) {
 2661                   int hi = run[k], mi = run[k - 1];
 2662                   for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
 2663                       if (q >= hi || p < mi && a[p] <= a[q]) {
 2664                           b[i] = a[p++];
 2665                       } else {
 2666                           b[i] = a[q++];
 2667                       }
 2668                   }
 2669                   run[++last] = hi;
 2670               }
 2671               if ((count & 1) != 0) {
 2672                   for (int i = right, lo = run[count - 1]; --i >= lo;
 2673                       b[i] = a[i]
 2674                   );
 2675                   run[++last] = right;
 2676               }
 2677               double[] t = a; a = b; b = t;
 2678           }
 2679       }
 2680   
 2681       /**
 2682        * Sorts the specified range of the array by Dual-Pivot Quicksort.
 2683        *
 2684        * @param a the array to be sorted
 2685        * @param left the index of the first element, inclusive, to be sorted
 2686        * @param right the index of the last element, inclusive, to be sorted
 2687        * @param leftmost indicates if this part is the leftmost in the range
 2688        */
 2689       private static void sort(double[] a, int left, int right, boolean leftmost) {
 2690           int length = right - left + 1;
 2691   
 2692           // Use insertion sort on tiny arrays
 2693           if (length < INSERTION_SORT_THRESHOLD) {
 2694               if (leftmost) {
 2695                   /*
 2696                    * Traditional (without sentinel) insertion sort,
 2697                    * optimized for server VM, is used in case of
 2698                    * the leftmost part.
 2699                    */
 2700                   for (int i = left, j = i; i < right; j = ++i) {
 2701                       double ai = a[i + 1];
 2702                       while (ai < a[j]) {
 2703                           a[j + 1] = a[j];
 2704                           if (j-- == left) {
 2705                               break;
 2706                           }
 2707                       }
 2708                       a[j + 1] = ai;
 2709                   }
 2710               } else {
 2711                   /*
 2712                    * Skip the longest ascending sequence.
 2713                    */
 2714                   do {
 2715                       if (left >= right) {
 2716                           return;
 2717                       }
 2718                   } while (a[++left] >= a[left - 1]);
 2719   
 2720                   /*
 2721                    * Every element from adjoining part plays the role
 2722                    * of sentinel, therefore this allows us to avoid the
 2723                    * left range check on each iteration. Moreover, we use
 2724                    * the more optimized algorithm, so called pair insertion
 2725                    * sort, which is faster (in the context of Quicksort)
 2726                    * than traditional implementation of insertion sort.
 2727                    */
 2728                   for (int k = left; ++left <= right; k = ++left) {
 2729                       double a1 = a[k], a2 = a[left];
 2730   
 2731                       if (a1 < a2) {
 2732                           a2 = a1; a1 = a[left];
 2733                       }
 2734                       while (a1 < a[--k]) {
 2735                           a[k + 2] = a[k];
 2736                       }
 2737                       a[++k + 1] = a1;
 2738   
 2739                       while (a2 < a[--k]) {
 2740                           a[k + 1] = a[k];
 2741                       }
 2742                       a[k + 1] = a2;
 2743                   }
 2744                   double last = a[right];
 2745   
 2746                   while (last < a[--right]) {
 2747                       a[right + 1] = a[right];
 2748                   }
 2749                   a[right + 1] = last;
 2750               }
 2751               return;
 2752           }
 2753   
 2754           // Inexpensive approximation of length / 7
 2755           int seventh = (length >> 3) + (length >> 6) + 1;
 2756   
 2757           /*
 2758            * Sort five evenly spaced elements around (and including) the
 2759            * center element in the range. These elements will be used for
 2760            * pivot selection as described below. The choice for spacing
 2761            * these elements was empirically determined to work well on
 2762            * a wide variety of inputs.
 2763            */
 2764           int e3 = (left + right) >>> 1; // The midpoint
 2765           int e2 = e3 - seventh;
 2766           int e1 = e2 - seventh;
 2767           int e4 = e3 + seventh;
 2768           int e5 = e4 + seventh;
 2769   
 2770           // Sort these elements using insertion sort
 2771           if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 2772   
 2773           if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
 2774               if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2775           }
 2776           if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
 2777               if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 2778                   if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2779               }
 2780           }
 2781           if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
 2782               if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
 2783                   if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
 2784                       if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 2785                   }
 2786               }
 2787           }
 2788   
 2789           // Pointers
 2790           int less  = left;  // The index of the first element of center part
 2791           int great = right; // The index before the first element of right part
 2792   
 2793           if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
 2794               /*
 2795                * Use the second and fourth of the five sorted elements as pivots.
 2796                * These values are inexpensive approximations of the first and
 2797                * second terciles of the array. Note that pivot1 <= pivot2.
 2798                */
 2799               double pivot1 = a[e2];
 2800               double pivot2 = a[e4];
 2801   
 2802               /*
 2803                * The first and the last elements to be sorted are moved to the
 2804                * locations formerly occupied by the pivots. When partitioning
 2805                * is complete, the pivots are swapped back into their final
 2806                * positions, and excluded from subsequent sorting.
 2807                */
 2808               a[e2] = a[left];
 2809               a[e4] = a[right];
 2810   
 2811               /*
 2812                * Skip elements, which are less or greater than pivot values.
 2813                */
 2814               while (a[++less] < pivot1);
 2815               while (a[--great] > pivot2);
 2816   
 2817               /*
 2818                * Partitioning:
 2819                *
 2820                *   left part           center part                   right part
 2821                * +--------------------------------------------------------------+
 2822                * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 2823                * +--------------------------------------------------------------+
 2824                *               ^                          ^       ^
 2825                *               |                          |       |
 2826                *              less                        k     great
 2827                *
 2828                * Invariants:
 2829                *
 2830                *              all in (left, less)   < pivot1
 2831                *    pivot1 <= all in [less, k)     <= pivot2
 2832                *              all in (great, right) > pivot2
 2833                *
 2834                * Pointer k is the first index of ?-part.
 2835                */
 2836               outer:
 2837               for (int k = less - 1; ++k <= great; ) {
 2838                   double ak = a[k];
 2839                   if (ak < pivot1) { // Move a[k] to left part
 2840                       a[k] = a[less];
 2841                       /*
 2842                        * Here and below we use "a[i] = b; i++;" instead
 2843                        * of "a[i++] = b;" due to performance issue.
 2844                        */
 2845                       a[less] = ak;
 2846                       ++less;
 2847                   } else if (ak > pivot2) { // Move a[k] to right part
 2848                       while (a[great] > pivot2) {
 2849                           if (great-- == k) {
 2850                               break outer;
 2851                           }
 2852                       }
 2853                       if (a[great] < pivot1) { // a[great] <= pivot2
 2854                           a[k] = a[less];
 2855                           a[less] = a[great];
 2856                           ++less;
 2857                       } else { // pivot1 <= a[great] <= pivot2
 2858                           a[k] = a[great];
 2859                       }
 2860                       /*
 2861                        * Here and below we use "a[i] = b; i--;" instead
 2862                        * of "a[i--] = b;" due to performance issue.
 2863                        */
 2864                       a[great] = ak;
 2865                       --great;
 2866                   }
 2867               }
 2868   
 2869               // Swap pivots into their final positions
 2870               a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 2871               a[right] = a[great + 1]; a[great + 1] = pivot2;
 2872   
 2873               // Sort left and right parts recursively, excluding known pivots
 2874               sort(a, left, less - 2, leftmost);
 2875               sort(a, great + 2, right, false);
 2876   
 2877               /*
 2878                * If center part is too large (comprises > 4/7 of the array),
 2879                * swap internal pivot values to ends.
 2880                */
 2881               if (less < e1 && e5 < great) {
 2882                   /*
 2883                    * Skip elements, which are equal to pivot values.
 2884                    */
 2885                   while (a[less] == pivot1) {
 2886                       ++less;
 2887                   }
 2888   
 2889                   while (a[great] == pivot2) {
 2890                       --great;
 2891                   }
 2892   
 2893                   /*
 2894                    * Partitioning:
 2895                    *
 2896                    *   left part         center part                  right part
 2897                    * +----------------------------------------------------------+
 2898                    * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
 2899                    * +----------------------------------------------------------+
 2900                    *              ^                        ^       ^
 2901                    *              |                        |       |
 2902                    *             less                      k     great
 2903                    *
 2904                    * Invariants:
 2905                    *
 2906                    *              all in (*,  less) == pivot1
 2907                    *     pivot1 < all in [less,  k)  < pivot2
 2908                    *              all in (great, *) == pivot2
 2909                    *
 2910                    * Pointer k is the first index of ?-part.
 2911                    */
 2912                   outer:
 2913                   for (int k = less - 1; ++k <= great; ) {
 2914                       double ak = a[k];
 2915                       if (ak == pivot1) { // Move a[k] to left part
 2916                           a[k] = a[less];
 2917                           a[less] = ak;
 2918                           ++less;
 2919                       } else if (ak == pivot2) { // Move a[k] to right part
 2920                           while (a[great] == pivot2) {
 2921                               if (great-- == k) {
 2922                                   break outer;
 2923                               }
 2924                           }
 2925                           if (a[great] == pivot1) { // a[great] < pivot2
 2926                               a[k] = a[less];
 2927                               /*
 2928                                * Even though a[great] equals to pivot1, the
 2929                                * assignment a[less] = pivot1 may be incorrect,
 2930                                * if a[great] and pivot1 are floating-point zeros
 2931                                * of different signs. Therefore in float and
 2932                                * double sorting methods we have to use more
 2933                                * accurate assignment a[less] = a[great].
 2934                                */
 2935                               a[less] = a[great];
 2936                               ++less;
 2937                           } else { // pivot1 < a[great] < pivot2
 2938                               a[k] = a[great];
 2939                           }
 2940                           a[great] = ak;
 2941                           --great;
 2942                       }
 2943                   }
 2944               }
 2945   
 2946               // Sort center part recursively
 2947               sort(a, less, great, false);
 2948   
 2949           } else { // Partitioning with one pivot
 2950               /*
 2951                * Use the third of the five sorted elements as pivot.
 2952                * This value is inexpensive approximation of the median.
 2953                */
 2954               double pivot = a[e3];
 2955   
 2956               /*
 2957                * Partitioning degenerates to the traditional 3-way
 2958                * (or "Dutch National Flag") schema:
 2959                *
 2960                *   left part    center part              right part
 2961                * +-------------------------------------------------+
 2962                * |  < pivot  |   == pivot   |     ?    |  > pivot  |
 2963                * +-------------------------------------------------+
 2964                *              ^              ^        ^
 2965                *              |              |        |
 2966                *             less            k      great
 2967                *
 2968                * Invariants:
 2969                *
 2970                *   all in (left, less)   < pivot
 2971                *   all in [less, k)     == pivot
 2972                *   all in (great, right) > pivot
 2973                *
 2974                * Pointer k is the first index of ?-part.
 2975                */
 2976               for (int k = less; k <= great; ++k) {
 2977                   if (a[k] == pivot) {
 2978                       continue;
 2979                   }
 2980                   double ak = a[k];
 2981                   if (ak < pivot) { // Move a[k] to left part
 2982                       a[k] = a[less];
 2983                       a[less] = ak;
 2984                       ++less;
 2985                   } else { // a[k] > pivot - Move a[k] to right part
 2986                       while (a[great] > pivot) {
 2987                           --great;
 2988                       }
 2989                       if (a[great] < pivot) { // a[great] <= pivot
 2990                           a[k] = a[less];
 2991                           a[less] = a[great];
 2992                           ++less;
 2993                       } else { // a[great] == pivot
 2994                           /*
 2995                            * Even though a[great] equals to pivot, the
 2996                            * assignment a[k] = pivot may be incorrect,
 2997                            * if a[great] and pivot are floating-point
 2998                            * zeros of different signs. Therefore in float
 2999                            * and double sorting methods we have to use
 3000                            * more accurate assignment a[k] = a[great].
 3001                            */
 3002                           a[k] = a[great];
 3003                       }
 3004                       a[great] = ak;
 3005                       --great;
 3006                   }
 3007               }
 3008   
 3009               /*
 3010                * Sort left and right parts recursively.
 3011                * All elements from center part are equal
 3012                * and, therefore, already sorted.
 3013                */
 3014               sort(a, left, less - 1, leftmost);
 3015               sort(a, great + 1, right, false);
 3016           }
 3017       }
 3018   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]