1 /*

     2  * Copyright 2009 Sun Microsystems, Inc.  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.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any 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 Joshua 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 2009.10.22 m765.827.v4

    40  */

    41 final class DualPivotQuicksort {

    42 

    43     // Suppresses default constructor, ensuring non-instantiability.

    44     private DualPivotQuicksort() {}

    45 

    46     /*

    47      * Tuning Parameters.

    48      */

    49 

    50     /**

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

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

    53      */

    54     private static final int INSERTION_SORT_THRESHOLD = 32;

    55 

    56     /**

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

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

    59      */

    60     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;

    61 

    62     /**

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

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

    65      */

    66     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;

    67 

    68     /*

    69      * Sorting methods for the seven primitive types.

    70      */

    71 

    72     /**

    73      * Sorts the specified range of the array into ascending order.

    74      *

    75      * @param a the array to be sorted

    76      * @param left the index of the first element, inclusively, to be sorted

    77      * @param right the index of the last element, inclusively, to be sorted

    78      */

    79     static void sort(int[] a, int left, int right) {

    80         // Use insertion sort on tiny arrays

    81         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {

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

    83                 int ak = a[k];

    84                 int j;

    85 

    86                 for (j = k - 1; j >= left && ak < a[j]; j--) {

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

    88                 }

    89                 a[j + 1] = ak;

    90             }

    91         } else { // Use Dual-Pivot Quicksort on large arrays

    92             dualPivotQuicksort(a, left, right);

    93         }

    94     }

    95 

    96     /**

    97      * Sorts the specified range of the array into ascending order

    98      * by Dual-Pivot Quicksort.

    99      *

   100      * @param a the array to be sorted

   101      * @param left the index of the first element, inclusively, to be sorted

   102      * @param right the index of the last element, inclusively, to be sorted

   103      */

   104     private static void dualPivotQuicksort(int[] a, int left, int right) {

   105         // Compute indices of five evenly spaced elements

   106         int sixth = (right - left + 1) / 6;

   107         int e1 = left  + sixth;

   108         int e5 = right - sixth;

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

   110         int e4 = e3 + sixth;

   111         int e2 = e3 - sixth;

   112 

   113         // Sort these elements in place using a 5-element sorting network

   114         if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t; }

   115         if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   116         if (a[e1] > a[e3]) { int t = a[e1]; a[e1] = a[e3]; a[e3] = t; }

   117         if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   118         if (a[e1] > a[e4]) { int t = a[e1]; a[e1] = a[e4]; a[e4] = t; }

   119         if (a[e3] > a[e4]) { int t = a[e3]; a[e3] = a[e4]; a[e4] = t; }

   120         if (a[e2] > a[e5]) { int t = a[e2]; a[e2] = a[e5]; a[e5] = t; }

   121         if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   122         if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   123 

   124         /*

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

   126          * These values are inexpensive approximations of the first and

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

   128          *

   129          * The pivots are stored in local variables, and the first and

   130          * the last of the sorted elements are moved to the locations

   131          * formerly occupied by the pivots. When partitioning is complete,

   132          * the pivots are swapped back into their final positions, and

   133          * excluded from subsequent sorting.

   134          */

   135         int pivot1 = a[e2]; a[e2] = a[left];

   136         int pivot2 = a[e4]; a[e4] = a[right];

   137 

   138         /*

   139          * Partitioning

   140          *

   141          *   left part         center part                  right part

   142          * ------------------------------------------------------------

   143          * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]

   144          * ------------------------------------------------------------

   145          *              ^                          ^     ^

   146          *              |                          |     |

   147          *             less                        k   great

   148          */

   149 

   150         // Pointers

   151         int less  = left  + 1; // The index of first element of center part

   152         int great = right - 1; // The index before first element of right part

   153 

   154         boolean pivotsDiffer = pivot1 != pivot2;

   155 

   156         if (pivotsDiffer) {

   157             /*

   158              * Invariants:

   159              *              all in (left, less)   < pivot1

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

   161              *              all in (great, right) > pivot2

   162              *

   163              * Pointer k is the first index of ?-part

   164              */

   165             for (int k = less; k <= great; k++) {

   166                 int ak = a[k];

   167 

   168                 if (ak < pivot1) {

   169                     a[k] = a[less];

   170                     a[less++] = ak;

   171                 } else if (ak > pivot2) {

   172                     while (a[great] > pivot2 && k < great) {

   173                         great--;

   174                     }

   175                     a[k] = a[great];

   176                     a[great--] = ak;

   177                     ak = a[k];

   178 

   179                     if (ak < pivot1) {

   180                         a[k] = a[less];

   181                         a[less++] = ak;

   182                     }

   183                 }

   184             }

   185         } else { // Pivots are equal

   186             /*

   187              * Partition degenerates to the traditional 3-way

   188              * (or "Dutch National Flag") partition:

   189              *

   190              *   left part   center part            right part

   191              * -------------------------------------------------

   192              * [  < pivot  |  == pivot  |    ?    |  > pivot   ]

   193              * -------------------------------------------------

   194              *

   195              *              ^            ^       ^

   196              *              |            |       |

   197              *             less          k     great

   198              *

   199              * Invariants:

   200              *

   201              *   all in (left, less)   < pivot

   202              *   all in [less, k)     == pivot

   203              *   all in (great, right) > pivot

   204              *

   205              * Pointer k is the first index of ?-part

   206              */

   207             for (int k = less; k <= great; k++) {

   208                 int ak = a[k];

   209 

   210                 if (ak == pivot1) {

   211                   continue;

   212                 }

   213                 if (ak < pivot1) {

   214                     a[k] = a[less];

   215                     a[less++] = ak;

   216                 } else {

   217                     while (a[great] > pivot1) {

   218                         great--;

   219                     }

   220                     a[k] = a[great];

   221                     a[great--] = ak;

   222                     ak = a[k];

   223 

   224                     if (ak < pivot1) {

   225                         a[k] = a[less];

   226                         a[less++] = ak;

   227                     }

   228                 }

   229             }

   230         }

   231 

   232         // Swap pivots into their final positions

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

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

   235 

   236         // Sort left and right parts recursively, excluding known pivot values

   237         sort(a, left,   less - 2);

   238         sort(a, great + 2, right);

   239 

   240         /*

   241          * If pivot1 == pivot2, all elements from center

   242          * part are equal and, therefore, already sorted

   243          */

   244         if (!pivotsDiffer) {

   245             return;

   246         }

   247 

   248         /*

   249          * If center part is too large (comprises > 5/6 of

   250          * the array), swap internal pivot values to ends

   251          */

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

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

   254                 less++;

   255             }

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

   257                 if (a[k] == pivot1) {

   258                     a[k] = a[less];

   259                     a[less++] = pivot1;

   260                 }

   261             }

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

   263                 great--;

   264             }

   265             for (int k = great - 1; k >= less; k--) {

   266                 if (a[k] == pivot2) {

   267                     a[k] = a[great];

   268                     a[great--] = pivot2;

   269                 }

   270             }

   271         }

   272 

   273         // Sort center part recursively, excluding known pivot values

   274         sort(a, less, great);

   275     }

   276 

   277     /**

   278      * Sorts the specified range of the array into ascending order.

   279      *

   280      * @param a the array to be sorted

   281      * @param left the index of the first element, inclusively, to be sorted

   282      * @param right the index of the last element, inclusively, to be sorted

   283      */

   284     static void sort(long[] a, int left, int right) {

   285         // Use insertion sort on tiny arrays

   286         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {

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

   288                 long ak = a[k];

   289                 int j;

   290 

   291                 for (j = k - 1; j >= left && ak < a[j]; j--) {

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

   293                 }

   294                 a[j + 1] = ak;

   295             }

   296         } else { // Use Dual-Pivot Quicksort on large arrays

   297             dualPivotQuicksort(a, left, right);

   298         }

   299     }

   300 

   301     /**

   302      * Sorts the specified range of the array into ascending order

   303      * by Dual-Pivot Quicksort.

   304      *

   305      * @param a the array to be sorted

   306      * @param left the index of the first element, inclusively, to be sorted

   307      * @param right the index of the last element, inclusively, to be sorted

   308      */

   309     private static void dualPivotQuicksort(long[] a, int left, int right) {

   310         // Compute indices of five evenly spaced elements

   311         int sixth = (right - left + 1) / 6;

   312         int e1 = left  + sixth;

   313         int e5 = right - sixth;

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

   315         int e4 = e3 + sixth;

   316         int e2 = e3 - sixth;

   317 

   318         // Sort these elements in place using a 5-element sorting network

   319         if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t; }

   320         if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   321         if (a[e1] > a[e3]) { long t = a[e1]; a[e1] = a[e3]; a[e3] = t; }

   322         if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   323         if (a[e1] > a[e4]) { long t = a[e1]; a[e1] = a[e4]; a[e4] = t; }

   324         if (a[e3] > a[e4]) { long t = a[e3]; a[e3] = a[e4]; a[e4] = t; }

   325         if (a[e2] > a[e5]) { long t = a[e2]; a[e2] = a[e5]; a[e5] = t; }

   326         if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   327         if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   328 

   329         /*

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

   331          * These values are inexpensive approximations of the first and

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

   333          *

   334          * The pivots are stored in local variables, and the first and

   335          * the last of the sorted elements are moved to the locations

   336          * formerly occupied by the pivots. When partitioning is complete,

   337          * the pivots are swapped back into their final positions, and

   338          * excluded from subsequent sorting.

   339          */

   340         long pivot1 = a[e2]; a[e2] = a[left];

   341         long pivot2 = a[e4]; a[e4] = a[right];

   342 

   343         /*

   344          * Partitioning

   345          *

   346          *   left part         center part                  right part

   347          * ------------------------------------------------------------

   348          * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]

   349          * ------------------------------------------------------------

   350          *              ^                          ^     ^

   351          *              |                          |     |

   352          *             less                        k   great

   353          */

   354 

   355         // Pointers

   356         int less  = left  + 1; // The index of first element of center part

   357         int great = right - 1; // The index before first element of right part

   358 

   359         boolean pivotsDiffer = pivot1 != pivot2;

   360 

   361         if (pivotsDiffer) {

   362             /*

   363              * Invariants:

   364              *              all in (left, less)   < pivot1

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

   366              *              all in (great, right) > pivot2

   367              *

   368              * Pointer k is the first index of ?-part

   369              */

   370             for (int k = less; k <= great; k++) {

   371                 long ak = a[k];

   372 

   373                 if (ak < pivot1) {

   374                     a[k] = a[less];

   375                     a[less++] = ak;

   376                 } else if (ak > pivot2) {

   377                     while (a[great] > pivot2 && k < great) {

   378                         great--;

   379                     }

   380                     a[k] = a[great];

   381                     a[great--] = ak;

   382                     ak = a[k];

   383 

   384                     if (ak < pivot1) {

   385                         a[k] = a[less];

   386                         a[less++] = ak;

   387                     }

   388                 }

   389             }

   390         } else { // Pivots are equal

   391             /*

   392              * Partition degenerates to the traditional 3-way

   393              * (or "Dutch National Flag") partition:

   394              *

   395              *   left part   center part            right part

   396              * -------------------------------------------------

   397              * [  < pivot  |  == pivot  |    ?    |  > pivot   ]

   398              * -------------------------------------------------

   399              *

   400              *              ^            ^       ^

   401              *              |            |       |

   402              *             less          k     great

   403              *

   404              * Invariants:

   405              *

   406              *   all in (left, less)   < pivot

   407              *   all in [less, k)     == pivot

   408              *   all in (great, right) > pivot

   409              *

   410              * Pointer k is the first index of ?-part

   411              */

   412             for (int k = less; k <= great; k++) {

   413                 long ak = a[k];

   414 

   415                 if (ak == pivot1) {

   416                   continue;

   417                 }

   418                 if (ak < pivot1) {

   419                     a[k] = a[less];

   420                     a[less++] = ak;

   421                 } else {

   422                     while (a[great] > pivot1) {

   423                         great--;

   424                     }

   425                     a[k] = a[great];

   426                     a[great--] = ak;

   427                     ak = a[k];

   428 

   429                     if (ak < pivot1) {

   430                         a[k] = a[less];

   431                         a[less++] = ak;

   432                     }

   433                 }

   434             }

   435         }

   436 

   437         // Swap pivots into their final positions

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

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

   440 

   441         // Sort left and right parts recursively, excluding known pivot values

   442         sort(a, left,   less - 2);

   443         sort(a, great + 2, right);

   444 

   445         /*

   446          * If pivot1 == pivot2, all elements from center

   447          * part are equal and, therefore, already sorted

   448          */

   449         if (!pivotsDiffer) {

   450             return;

   451         }

   452 

   453         /*

   454          * If center part is too large (comprises > 5/6 of

   455          * the array), swap internal pivot values to ends

   456          */

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

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

   459                 less++;

   460             }

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

   462                 if (a[k] == pivot1) {

   463                     a[k] = a[less];

   464                     a[less++] = pivot1;

   465                 }

   466             }

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

   468                 great--;

   469             }

   470             for (int k = great - 1; k >= less; k--) {

   471                 if (a[k] == pivot2) {

   472                     a[k] = a[great];

   473                     a[great--] = pivot2;

   474                 }

   475             }

   476         } else { // Use Dual-Pivot Quicksort on large arrays

   477             dualPivotQuicksort(a, left, right);

   478         }

   479     }

   480 

   481     /** The number of distinct short values */

   482     private static final int NUM_SHORT_VALUES = 1 << 16;

   483 

   484     /**

   485      * Sorts the specified range of the array into ascending order.

   486      *

   487      * @param a the array to be sorted

   488      * @param left the index of the first element, inclusively, to be sorted

   489      * @param right the index of the last element, inclusively, to be sorted

   490      */

   491     static void sort(short[] a, int left, int right) {

   492         // Use insertion sort on tiny arrays

   493         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {

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

   495                 short ak = a[k];

   496                 int j;

   497 

   498                 for (j = k - 1; j >= left && ak < a[j]; j--) {

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

   500                 }

   501                 a[j + 1] = ak;

   502             }

   503         } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {

   504             // Use counting sort on huge arrays

   505             int[] count = new int[NUM_SHORT_VALUES];

   506 

   507             for (int i = left; i <= right; i++) {

   508                 count[a[i] - Short.MIN_VALUE]++;

   509             }

   510             for (int i = 0, k = left; i < count.length && k < right; i++) {

   511                 short value = (short) (i + Short.MIN_VALUE);

   512 

   513                 for (int s = count[i]; s > 0; s--) {

   514                     a[k++] = value;

   515                }

   516             }

   517         } else { // Use Dual-Pivot Quicksort on large arrays

   518             dualPivotQuicksort(a, left, right);

   519         }

   520     }

   521 

   522     /**

   523      * Sorts the specified range of the array into ascending order

   524      * by Dual-Pivot Quicksort.

   525      *

   526      * @param a the array to be sorted

   527      * @param left the index of the first element, inclusively, to be sorted

   528      * @param right the index of the last element, inclusively, to be sorted

   529      */

   530     private static void dualPivotQuicksort(short[] a, int left, int right) {

   531         // Compute indices of five evenly spaced elements

   532         int sixth = (right - left + 1) / 6;

   533         int e1 = left  + sixth;

   534         int e5 = right - sixth;

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

   536         int e4 = e3 + sixth;

   537         int e2 = e3 - sixth;

   538 

   539         // Sort these elements in place using a 5-element sorting network

   540         if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t; }

   541         if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   542         if (a[e1] > a[e3]) { short t = a[e1]; a[e1] = a[e3]; a[e3] = t; }

   543         if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   544         if (a[e1] > a[e4]) { short t = a[e1]; a[e1] = a[e4]; a[e4] = t; }

   545         if (a[e3] > a[e4]) { short t = a[e3]; a[e3] = a[e4]; a[e4] = t; }

   546         if (a[e2] > a[e5]) { short t = a[e2]; a[e2] = a[e5]; a[e5] = t; }

   547         if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   548         if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   549 

   550         /*

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

   552          * These values are inexpensive approximations of the first and

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

   554          *

   555          * The pivots are stored in local variables, and the first and

   556          * the last of the sorted elements are moved to the locations

   557          * formerly occupied by the pivots. When partitioning is complete,

   558          * the pivots are swapped back into their final positions, and

   559          * excluded from subsequent sorting.

   560          */

   561         short pivot1 = a[e2]; a[e2] = a[left];

   562         short pivot2 = a[e4]; a[e4] = a[right];

   563 

   564         /*

   565          * Partitioning

   566          *

   567          *   left part         center part                  right part

   568          * ------------------------------------------------------------

   569          * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]

   570          * ------------------------------------------------------------

   571          *              ^                          ^     ^

   572          *              |                          |     |

   573          *             less                        k   great

   574          */

   575 

   576         // Pointers

   577         int less  = left  + 1; // The index of first element of center part

   578         int great = right - 1; // The index before first element of right part

   579 

   580         boolean pivotsDiffer = pivot1 != pivot2;

   581 

   582         if (pivotsDiffer) {

   583             /*

   584              * Invariants:

   585              *              all in (left, less)   < pivot1

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

   587              *              all in (great, right) > pivot2

   588              *

   589              * Pointer k is the first index of ?-part

   590              */

   591             for (int k = less; k <= great; k++) {

   592                 short ak = a[k];

   593 

   594                 if (ak < pivot1) {

   595                     a[k] = a[less];

   596                     a[less++] = ak;

   597                 } else if (ak > pivot2) {

   598                     while (a[great] > pivot2 && k < great) {

   599                         great--;

   600                     }

   601                     a[k] = a[great];

   602                     a[great--] = ak;

   603                     ak = a[k];

   604 

   605                     if (ak < pivot1) {

   606                         a[k] = a[less];

   607                         a[less++] = ak;

   608                     }

   609                 }

   610             }

   611         } else { // Pivots are equal

   612             /*

   613              * Partition degenerates to the traditional 3-way

   614              * (or "Dutch National Flag") partition:

   615              *

   616              *   left part   center part            right part

   617              * -------------------------------------------------

   618              * [  < pivot  |  == pivot  |    ?    |  > pivot   ]

   619              * -------------------------------------------------

   620              *

   621              *              ^            ^       ^

   622              *              |            |       |

   623              *             less          k     great

   624              *

   625              * Invariants:

   626              *

   627              *   all in (left, less)   < pivot

   628              *   all in [less, k)     == pivot

   629              *   all in (great, right) > pivot

   630              *

   631              * Pointer k is the first index of ?-part

   632              */

   633             for (int k = less; k <= great; k++) {

   634                 short ak = a[k];

   635 

   636                 if (ak == pivot1) {

   637                   continue;

   638                 }

   639                 if (ak < pivot1) {

   640                     a[k] = a[less];

   641                     a[less++] = ak;

   642                 } else {

   643                     while (a[great] > pivot1) {

   644                         great--;

   645                     }

   646                     a[k] = a[great];

   647                     a[great--] = ak;

   648                     ak = a[k];

   649 

   650                     if (ak < pivot1) {

   651                         a[k] = a[less];

   652                         a[less++] = ak;

   653                     }

   654                 }

   655             }

   656         }

   657 

   658         // Swap pivots into their final positions

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

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

   661 

   662         // Sort left and right parts recursively, excluding known pivot values

   663         sort(a, left,   less - 2);

   664         sort(a, great + 2, right);

   665 

   666         /*

   667          * If pivot1 == pivot2, all elements from center

   668          * part are equal and, therefore, already sorted

   669          */

   670         if (!pivotsDiffer) {

   671             return;

   672         }

   673 

   674         /*

   675          * If center part is too large (comprises > 5/6 of

   676          * the array), swap internal pivot values to ends

   677          */

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

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

   680                 less++;

   681             }

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

   683                 if (a[k] == pivot1) {

   684                     a[k] = a[less];

   685                     a[less++] = pivot1;

   686                 }

   687             }

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

   689                 great--;

   690             }

   691             for (int k = great - 1; k >= less; k--) {

   692                 if (a[k] == pivot2) {

   693                     a[k] = a[great];

   694                     a[great--] = pivot2;

   695                 }

   696             }

   697         }

   698 

   699         // Sort center part recursively, excluding known pivot values

   700         sort(a, less, great);

   701     }

   702 

   703     /** The number of distinct byte values */

   704     private static final int NUM_BYTE_VALUES = 1 << 8;

   705 

   706     /**

   707      * Sorts the specified range of the array into ascending order.

   708      *

   709      * @param a the array to be sorted

   710      * @param left the index of the first element, inclusively, to be sorted

   711      * @param right the index of the last element, inclusively, to be sorted

   712      */

   713     static void sort(byte[] a, int left, int right) {

   714         // Use insertion sort on tiny arrays

   715         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {

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

   717                 byte ak = a[k];

   718                 int j;

   719 

   720                 for (j = k - 1; j >= left && ak < a[j]; j--) {

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

   722                 }

   723                 a[j + 1] = ak;

   724             }

   725         } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {

   726             // Use counting sort on large arrays

   727             int[] count = new int[NUM_BYTE_VALUES];

   728 

   729             for (int i = left; i <= right; i++) {

   730                 count[a[i] - Byte.MIN_VALUE]++;

   731             }

   732             for (int i = 0, k = left; i < count.length && k < right; i++) {

   733                 byte value = (byte) (i + Byte.MIN_VALUE);

   734 

   735                 for (int s = count[i]; s > 0; s--) {

   736                     a[k++] = value;

   737                }

   738             }

   739         } else { // Use Dual-Pivot Quicksort on large arrays

   740             dualPivotQuicksort(a, left, right);

   741         }

   742     }

   743 

   744     /**

   745      * Sorts the specified range of the array into ascending order

   746      * by Dual-Pivot Quicksort.

   747      *

   748      * @param a the array to be sorted

   749      * @param left the index of the first element, inclusively, to be sorted

   750      * @param right the index of the last element, inclusively, to be sorted

   751      */

   752     private static void dualPivotQuicksort(byte[] a, int left, int right) {

   753         // Compute indices of five evenly spaced elements

   754         int sixth = (right - left + 1) / 6;

   755         int e1 = left  + sixth;

   756         int e5 = right - sixth;

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

   758         int e4 = e3 + sixth;

   759         int e2 = e3 - sixth;

   760 

   761         // Sort these elements in place using a 5-element sorting network

   762         if (a[e1] > a[e2]) { byte t = a[e1]; a[e1] = a[e2]; a[e2] = t; }

   763         if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   764         if (a[e1] > a[e3]) { byte t = a[e1]; a[e1] = a[e3]; a[e3] = t; }

   765         if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   766         if (a[e1] > a[e4]) { byte t = a[e1]; a[e1] = a[e4]; a[e4] = t; }

   767         if (a[e3] > a[e4]) { byte t = a[e3]; a[e3] = a[e4]; a[e4] = t; }

   768         if (a[e2] > a[e5]) { byte t = a[e2]; a[e2] = a[e5]; a[e5] = t; }

   769         if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   770         if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   771 

   772         /*

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

   774          * These values are inexpensive approximations of the first and

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

   776          *

   777          * The pivots are stored in local variables, and the first and

   778          * the last of the sorted elements are moved to the locations

   779          * formerly occupied by the pivots. When partitioning is complete,

   780          * the pivots are swapped back into their final positions, and

   781          * excluded from subsequent sorting.

   782          */

   783         byte pivot1 = a[e2]; a[e2] = a[left];

   784         byte pivot2 = a[e4]; a[e4] = a[right];

   785 

   786         /*

   787          * Partitioning

   788          *

   789          *   left part         center part                  right part

   790          * ------------------------------------------------------------

   791          * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]

   792          * ------------------------------------------------------------

   793          *              ^                          ^     ^

   794          *              |                          |     |

   795          *             less                        k   great

   796          */

   797 

   798         // Pointers

   799         int less  = left  + 1; // The index of first element of center part

   800         int great = right - 1; // The index before first element of right part

   801 

   802         boolean pivotsDiffer = pivot1 != pivot2;

   803 

   804         if (pivotsDiffer) {

   805             /*

   806              * Invariants:

   807              *              all in (left, less)   < pivot1

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

   809              *              all in (great, right) > pivot2

   810              *

   811              * Pointer k is the first index of ?-part

   812              */

   813             for (int k = less; k <= great; k++) {

   814                 byte ak = a[k];

   815 

   816                 if (ak < pivot1) {

   817                     a[k] = a[less];

   818                     a[less++] = ak;

   819                 } else if (ak > pivot2) {

   820                     while (a[great] > pivot2 && k < great) {

   821                         great--;

   822                     }

   823                     a[k] = a[great];

   824                     a[great--] = ak;

   825                     ak = a[k];

   826 

   827                     if (ak < pivot1) {

   828                         a[k] = a[less];

   829                         a[less++] = ak;

   830                     }

   831                 }

   832             }

   833         } else { // Pivots are equal

   834             /*

   835              * Partition degenerates to the traditional 3-way

   836              * (or "Dutch National Flag") partition:

   837              *

   838              *   left part   center part            right part

   839              * -------------------------------------------------

   840              * [  < pivot  |  == pivot  |    ?    |  > pivot   ]

   841              * -------------------------------------------------

   842              *

   843              *              ^            ^       ^

   844              *              |            |       |

   845              *             less          k     great

   846              *

   847              * Invariants:

   848              *

   849              *   all in (left, less)   < pivot

   850              *   all in [less, k)     == pivot

   851              *   all in (great, right) > pivot

   852              *

   853              * Pointer k is the first index of ?-part

   854              */

   855             for (int k = less; k <= great; k++) {

   856                 byte ak = a[k];

   857 

   858                 if (ak == pivot1) {

   859                   continue;

   860                 }

   861                 if (ak < pivot1) {

   862                     a[k] = a[less];

   863                     a[less++] = ak;

   864                 } else {

   865                     while (a[great] > pivot1) {

   866                         great--;

   867                     }

   868                     a[k] = a[great];

   869                     a[great--] = ak;

   870                     ak = a[k];

   871 

   872                     if (ak < pivot1) {

   873                         a[k] = a[less];

   874                         a[less++] = ak;

   875                     }

   876                 }

   877             }

   878         }

   879 

   880         // Swap pivots into their final positions

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

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

   883 

   884         // Sort left and right parts recursively, excluding known pivot values

   885         sort(a, left,   less - 2);

   886         sort(a, great + 2, right);

   887 

   888         /*

   889          * If pivot1 == pivot2, all elements from center

   890          * part are equal and, therefore, already sorted

   891          */

   892         if (!pivotsDiffer) {

   893             return;

   894         }

   895 

   896         /*

   897          * If center part is too large (comprises > 5/6 of

   898          * the array), swap internal pivot values to ends

   899          */

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

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

   902                 less++;

   903             }

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

   905                 if (a[k] == pivot1) {

   906                     a[k] = a[less];

   907                     a[less++] = pivot1;

   908                 }

   909             }

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

   911                 great--;

   912             }

   913             for (int k = great - 1; k >= less; k--) {

   914                 if (a[k] == pivot2) {

   915                     a[k] = a[great];

   916                     a[great--] = pivot2;

   917                 }

   918             }

   919         }

   920 

   921         // Sort center part recursively, excluding known pivot values

   922         sort(a, less, great);

   923     }

   924 

   925     /** The number of distinct char values */

   926     private static final int NUM_CHAR_VALUES = 1 << 16;

   927 

   928     /**

   929      * Sorts the specified range of the array into ascending order.

   930      *

   931      * @param a the array to be sorted

   932      * @param left the index of the first element, inclusively, to be sorted

   933      * @param right the index of the last element, inclusively, to be sorted

   934      */

   935     static void sort(char[] a, int left, int right) {

   936         // Use insertion sort on tiny arrays

   937         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {

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

   939                 char ak = a[k];

   940                 int j;

   941 

   942                 for (j = k - 1; j >= left && ak < a[j]; j--) {

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

   944                 }

   945                 a[j + 1] = ak;

   946             }

   947         } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {

   948             // Use counting sort on huge arrays

   949             int[] count = new int[NUM_CHAR_VALUES];

   950 

   951             for (int i = left; i <= right; i++) {

   952                 count[a[i]]++;

   953             }

   954             for (int i = 0, k = left; i < count.length && k < right; i++) {

   955                 for (int s = count[i]; s > 0; s--) {

   956                     a[k++] = (char) i;

   957                }

   958             }

   959         } else { // Use Dual-Pivot Quicksort on large arrays

   960             dualPivotQuicksort(a, left, right);

   961         }

   962     }

   963 

   964     /**

   965      * Sorts the specified range of the array into ascending order

   966      * by Dual-Pivot Quicksort.

   967      *

   968      * @param a the array to be sorted

   969      * @param left the index of the first element, inclusively, to be sorted

   970      * @param right the index of the last element, inclusively, to be sorted

   971      */

   972     private static void dualPivotQuicksort(char[] a, int left, int right) {

   973         // Compute indices of five evenly spaced elements

   974         int sixth = (right - left + 1) / 6;

   975         int e1 = left  + sixth;

   976         int e5 = right - sixth;

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

   978         int e4 = e3 + sixth;

   979         int e2 = e3 - sixth;

   980 

   981         // Sort these elements in place using a 5-element sorting network

   982         if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; }

   983         if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   984         if (a[e1] > a[e3]) { char t = a[e1]; a[e1] = a[e3]; a[e3] = t; }

   985         if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   986         if (a[e1] > a[e4]) { char t = a[e1]; a[e1] = a[e4]; a[e4] = t; }

   987         if (a[e3] > a[e4]) { char t = a[e3]; a[e3] = a[e4]; a[e4] = t; }

   988         if (a[e2] > a[e5]) { char t = a[e2]; a[e2] = a[e5]; a[e5] = t; }

   989         if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }

   990         if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }

   991 

   992         /*

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

   994          * These values are inexpensive approximations of the first and

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

   996          *

   997          * The pivots are stored in local variables, and the first and

   998          * the last of the sorted elements are moved to the locations

   999          * formerly occupied by the pivots. When partitioning is complete,

  1000          * the pivots are swapped back into their final positions, and

  1001          * excluded from subsequent sorting.

  1002          */

  1003         char pivot1 = a[e2]; a[e2] = a[left];

  1004         char pivot2 = a[e4]; a[e4] = a[right];

  1005 

  1006         /*

  1007          * Partitioning

  1008          *

  1009          *   left part         center part                  right part

  1010          * ------------------------------------------------------------

  1011          * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]

  1012          * ------------------------------------------------------------

  1013          *              ^                          ^     ^

  1014          *              |                          |     |

  1015          *             less                        k   great

  1016          */

  1017 

  1018         // Pointers

  1019         int less  = left  + 1; // The index of first element of center part

  1020         int great = right - 1; // The index before first element of right part

  1021 

  1022         boolean pivotsDiffer = pivot1 != pivot2;

  1023 

  1024         if (pivotsDiffer) {

  1025             /*

  1026              * Invariants:

  1027              *              all in (left, less)   < pivot1

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

  1029              *              all in (great, right) > pivot2

  1030              *

  1031              * Pointer k is the first index of ?-part

  1032              */

  1033             for (int k = less; k <= great; k++) {

  1034                 char ak = a[k];

  1035 

  1036                 if (ak < pivot1) {

  1037                     a[k] = a[less];

  1038                     a[less++] = ak;

  1039                 } else if (ak > pivot2) {

  1040                     while (a[great] > pivot2 && k < great) {

  1041                         great--;

  1042                     }

  1043                     a[k] = a[great];

  1044                     a[great--] = ak;

  1045                     ak = a[k];

  1046 

  1047                     if (ak < pivot1) {

  1048                         a[k] = a[less];

  1049                         a[less++] = ak;

  1050                     }

  1051                 }

  1052             }

  1053         } else { // Pivots are equal

  1054             /*

  1055              * Partition degenerates to the traditional 3-way

  1056              * (or "Dutch National Flag") partition:

  1057              *

  1058              *   left part   center part            right part

  1059              * -------------------------------------------------

  1060              * [  < pivot  |  == pivot  |    ?    |  > pivot   ]

  1061              * -------------------------------------------------

  1062              *

  1063              *              ^            ^       ^

  1064              *              |            |       |

  1065              *             less          k     great

  1066              *

  1067              * Invariants:

  1068              *

  1069              *   all in (left, less)   < pivot

  1070              *   all in [less, k)     == pivot

  1071              *   all in (great, right) > pivot

  1072              *

  1073              * Pointer k is the first index of ?-part

  1074              */

  1075             for (int k = less; k <= great; k++) {

  1076                 char ak = a[k];

  1077 

  1078                 if (ak == pivot1) {

  1079                   continue;

  1080                 }

  1081                 if (ak < pivot1) {

  1082                     a[k] = a[less];

  1083                     a[less++] = ak;

  1084                 } else {

  1085                     while (a[great] > pivot1) {

  1086                         great--;

  1087                     }

  1088                     a[k] = a[great];

  1089                     a[great--] = ak;

  1090                     ak = a[k];

  1091 

  1092                     if (ak < pivot1) {

  1093                         a[k] = a[less];

  1094                         a[less++] = ak;

  1095                     }

  1096                 }

  1097             }

  1098         }

  1099 

  1100         // Swap pivots into their final positions

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

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

  1103 

  1104         // Sort left and right parts recursively, excluding known pivot values

  1105         sort(a, left,   less - 2);

  1106         sort(a, great + 2, right);

  1107 

  1108         /*

  1109          * If pivot1 == pivot2, all elements from center

  1110          * part are equal and, therefore, already sorted

  1111          */

  1112         if (!pivotsDiffer) {

  1113             return;

  1114         }

  1115 

  1116         /*

  1117          * If center part is too large (comprises > 5/6 of

  1118          * the array), swap internal pivot values to ends

  1119          */

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

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

  1122                 less++;

  1123             }

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

  1125                 if (a[k] == pivot1) {

  1126                     a[k] = a[less];

  1127                     a[less++] = pivot1;

  1128                 }

  1129             }

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

  1131                 great--;

  1132             }

  1133             for (int k = great - 1; k >= less; k--) {

  1134                 if (a[k] == pivot2) {

  1135                     a[k] = a[great];