/*

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

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * under the terms of the GNU General Public License version 2 only, as

  * published by the Free Software Foundation.  Oracle designates this

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

  * by Oracle in the LICENSE file that accompanied this code.

  *

  * This code is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

  * version 2 for more details (a copy is included in the LICENSE file that

  * accompanied this code).

  *

  * You should have received a copy of the GNU General Public License version

  * 2 along with this work; if not, write to the Free Software Foundation,

  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

  *

  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  */

 package java.util;

 /**

  * This class implements the Dual-Pivot Quicksort algorithm by

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

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

  * quicksorts to degrade to quadratic performance, and is typically

  * faster than traditional (one-pivot) Quicksort implementations.

  *

  * @author Vladimir Yaroslavskiy

  * @author Jon Bentley

  * @author Josh Bloch

  *

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

  * @since 1.7

  */

 final class DualPivotQuicksort {

     /**

      * Prevents instantiation.

      */

     private DualPivotQuicksort() {}

     /*

      * Tuning parameters.

      */

     /**

      * The maximum number of runs in merge sort.

      */

     private static final int MAX_RUN_COUNT = 67;

     /**

      * The maximum length of run in merge sort.

      */

     private static final int MAX_RUN_LENGTH = 33;

     /**

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

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

      */

     private static final int QUICKSORT_THRESHOLD = 286;

     /**

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

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

      */

     private static final int INSERTION_SORT_THRESHOLD = 47;

     /**

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

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

      */

     private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

     /**

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

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

      */

     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

     /*

      * Sorting methods for seven primitive types.

      */

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(int[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

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

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         int[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new int[b.length];

             for (int i = left - 1; ++i < right; a[i] = b[i]);

         } else {

             b = new int[a.length];

         }

         // Merging

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

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

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

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

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

                         b[i] = a[p++];

                     } else {

                         b[i] = a[q++];

                     }

                 }

                 run[++last] = hi;

             }

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

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

                     b[i] = a[i]

                 );

                 run[++last] = right;

             }

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

         }

     }

     /**

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

      *

      * @param a the array to be sorted

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

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

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

      */

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

         int length = right - left + 1;

         // Use insertion sort on tiny arrays

         if (length < INSERTION_SORT_THRESHOLD) {

             if (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort,

                  * optimized for server VM, is used in case of

                  * the leftmost part.

                  */

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

                     int ai = a[i + 1];

                     while (ai < a[j]) {

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

                         if (j-- == left) {

                             break;

                         }

                     }

                     a[j + 1] = ai;

                 }

             } else {

                 /*

                  * Skip the longest ascending sequence.

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

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

                 /*

                  * Every element from adjoining part plays the role

                  * of sentinel, therefore this allows us to avoid the

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

                  * the more optimized algorithm, so called pair insertion

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

                  * than traditional implementation of insertion sort.

                  */

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

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

                     if (a1 < a2) {

                         a2 = a1; a1 = a[left];

                     }

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

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

                     }

                     a[++k + 1] = a1;

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

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

                     }

                     a[k + 1] = a2;

                 }

                 int last = a[right];

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

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

                 }

                 a[right + 1] = last;

             }

             return;

         }

         // Inexpensive approximation of length / 7

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

         /*

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

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

          * pivot selection as described below. The choice for spacing

          * these elements was empirically determined to work well on

          * a wide variety of inputs.

          */

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

         int e2 = e3 - seventh;

         int e1 = e2 - seventh;

         int e4 = e3 + seventh;

         int e5 = e4 + seventh;

         // Sort these elements using insertion sort

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

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

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

         }

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

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

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

             }

         }

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

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

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

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

                 }

             }

         }

         // Pointers

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

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

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

             /*

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

              * These values are inexpensive approximations of the first and

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

              */

             int pivot1 = a[e2];

             int pivot2 = a[e4];

             /*

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

              * locations formerly occupied by the pivots. When partitioning

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

              * positions, and excluded from subsequent sorting.

              */

             a[e2] = a[left];

             a[e4] = a[right];

             /*

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

              */

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

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

             /*

              * Partitioning:

              *

              *   left part           center part                   right part

              * +--------------------------------------------------------------+

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

              * +--------------------------------------------------------------+

              *               ^                          ^       ^

              *               |                          |       |

              *              less                        k     great

              *

              * Invariants:

              *

              *              all in (left, less)   < pivot1

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

              *              all in (great, right) > pivot2

              *

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

              */

             outer:

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

                 int ak = a[k];

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

                     a[k] = a[less];

                     /*

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

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

                      */

                     a[less] = ak;

                     ++less;

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

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                             break outer;

                         }

                     }

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

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

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

                         a[k] = a[great];

                     }

                     /*

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

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

                      */

                     a[great] = ak;

                     --great;

                 }

             }

             // Swap pivots into their final positions

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

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

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

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

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

             /*

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

              * swap internal pivot values to ends.

              */

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

                 /*

                  * Skip elements, which are equal to pivot values.

                  */

                 while (a[less] == pivot1) {

                     ++less;

                 }

                 while (a[great] == pivot2) {

                     --great;

                 }

                 /*

                  * Partitioning:

                  *

                  *   left part         center part                  right part

                  * +----------------------------------------------------------+

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

                  * +----------------------------------------------------------+

                  *              ^                        ^       ^

                  *              |                        |       |

                  *             less                      k     great

                  *

                  * Invariants:

                  *

                  *              all in (*,  less) == pivot1

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

                  *              all in (great, *) == pivot2

                  *

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

                  */

                 outer:

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

                     int ak = a[k];

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

                         a[k] = a[less];

                         a[less] = ak;

                         ++less;

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

                         while (a[great] == pivot2) {

                             if (great-- == k) {

                                 break outer;

                             }

                         }

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

                             a[k] = a[less];

                             /*

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

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

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

                              * of different signs. Therefore in float and

                              * double sorting methods we have to use more

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

                              */

                             a[less] = pivot1;

                             ++less;

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

                             a[k] = a[great];

                         }

                         a[great] = ak;

                         --great;

                     }

                 }

             }

             // Sort center part recursively

             sort(a, less, great, false);

         } else { // Partitioning with one pivot

             /*

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

              * This value is inexpensive approximation of the median.

              */

             int pivot = a[e3];

             /*

              * Partitioning degenerates to the traditional 3-way

              * (or "Dutch National Flag") schema:

              *

              *   left part    center part              right part

              * +-------------------------------------------------+

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

              * +-------------------------------------------------+

              *              ^              ^        ^

              *              |              |        |

              *             less            k      great

              *

              * Invariants:

              *

              *   all in (left, less)   < pivot

              *   all in [less, k)     == pivot

              *   all in (great, right) > pivot

              *

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

              */

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

                 if (a[k] == pivot) {

                     continue;

                 }

                 int ak = a[k];

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

                     a[k] = a[less];

                     a[less] = ak;

                     ++less;

                 } else { // a[k] > pivot - Move a[k] to right part

                     while (a[great] > pivot) {

                         --great;

                     }

                     if (a[great] < pivot) { // a[great] <= pivot

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

                     } else { // a[great] == pivot

                         /*

                          * Even though a[great] equals to pivot, the

                          * assignment a[k] = pivot may be incorrect,

                          * if a[great] and pivot are floating-point

                          * zeros of different signs. Therefore in float

                          * and double sorting methods we have to use

                          * more accurate assignment a[k] = a[great].

                          */

                         a[k] = pivot;

                     }

                     a[great] = ak;

                     --great;

                 }

             }

             /*

              * Sort left and right parts recursively.

              * All elements from center part are equal

              * and, therefore, already sorted.

              */

             sort(a, left, less - 1, leftmost);

             sort(a, great + 1, right, false);

         }

     }

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(long[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

                     long t = a[lo]; a[lo] = a[hi]; a[hi] = t;

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         long[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new long[b.length];

             for (int i = left - 1; ++i < right; a[i] = b[i]);

         } else {

             b = new long[a.length];

         }

         // Merging

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

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

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

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

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

                         b[i] = a[p++];

                     } else {

                         b[i] = a[q++];

                     }

                 }

                 run[++last] = hi;

             }

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

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

                     b[i] = a[i]

                 );

                 run[++last] = right;

             }

             long[] t = a; a = b; b = t;

         }

     }

     /**

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

      *

      * @param a the array to be sorted

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

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

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

      */

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

         int length = right - left + 1;

         // Use insertion sort on tiny arrays

         if (length < INSERTION_SORT_THRESHOLD) {

             if (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort,

                  * optimized for server VM, is used in case of

                  * the leftmost part.

                  */

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

                     long ai = a[i + 1];

                     while (ai < a[j]) {

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

                         if (j-- == left) {

                             break;

                         }

                     }

                     a[j + 1] = ai;

                 }

             } else {

                 /*

                  * Skip the longest ascending sequence.

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

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

                 /*

                  * Every element from adjoining part plays the role

                  * of sentinel, therefore this allows us to avoid the

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

                  * the more optimized algorithm, so called pair insertion

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

                  * than traditional implementation of insertion sort.

                  */

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

                     long a1 = a[k], a2 = a[left];

                     if (a1 < a2) {

                         a2 = a1; a1 = a[left];

                     }

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

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

                     }

                     a[++k + 1] = a1;

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

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

                     }

                     a[k + 1] = a2;

                 }

                 long last = a[right];

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

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

                 }

                 a[right + 1] = last;

             }

             return;

         }

         // Inexpensive approximation of length / 7

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

         /*

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

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

          * pivot selection as described below. The choice for spacing

          * these elements was empirically determined to work well on

          * a wide variety of inputs.

          */

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

         int e2 = e3 - seventh;

         int e1 = e2 - seventh;

         int e4 = e3 + seventh;

         int e5 = e4 + seventh;

         // Sort these elements using insertion sort

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

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

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

         }

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

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

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

             }

         }

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

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

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

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

                 }

             }

         }

         // Pointers

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

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

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

             /*

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

              * These values are inexpensive approximations of the first and

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

              */

             long pivot1 = a[e2];

             long pivot2 = a[e4];

             /*

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

              * locations formerly occupied by the pivots. When partitioning

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

              * positions, and excluded from subsequent sorting.

              */

             a[e2] = a[left];

             a[e4] = a[right];

             /*

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

              */

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

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

             /*

              * Partitioning:

              *

              *   left part           center part                   right part

              * +--------------------------------------------------------------+

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

              * +--------------------------------------------------------------+

              *               ^                          ^       ^

              *               |                          |       |

              *              less                        k     great

              *

              * Invariants:

              *

              *              all in (left, less)   < pivot1

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

              *              all in (great, right) > pivot2

              *

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

              */

             outer:

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

                 long ak = a[k];

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

                     a[k] = a[less];

                     /*

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

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

                      */

                     a[less] = ak;

                     ++less;

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

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                             break outer;

                         }

                     }

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

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

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

                         a[k] = a[great];

                     }

                     /*

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

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

                      */

                     a[great] = ak;

                     --great;

                 }

             }

             // Swap pivots into their final positions

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

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

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

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

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

             /*

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

              * swap internal pivot values to ends.

              */

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

                 /*

                  * Skip elements, which are equal to pivot values.

                  */

                 while (a[less] == pivot1) {

                     ++less;

                 }

                 while (a[great] == pivot2) {

                     --great;

                 }

                 /*

                  * Partitioning:

                  *

                  *   left part         center part                  right part

                  * +----------------------------------------------------------+

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

                  * +----------------------------------------------------------+

                  *              ^                        ^       ^

                  *              |                        |       |

                  *             less                      k     great

                  *

                  * Invariants:

                  *

                  *              all in (*,  less) == pivot1

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

                  *              all in (great, *) == pivot2

                  *

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

                  */

                 outer:

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

                     long ak = a[k];

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

                         a[k] = a[less];

                         a[less] = ak;

                         ++less;

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

                         while (a[great] == pivot2) {

                             if (great-- == k) {

                                 break outer;

                             }

                         }

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

                             a[k] = a[less];

                             /*

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

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

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

                              * of different signs. Therefore in float and

                              * double sorting methods we have to use more

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

                              */

                             a[less] = pivot1;

                             ++less;

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

                             a[k] = a[great];

                         }

                         a[great] = ak;

                         --great;

                     }

                 }

             }

             // Sort center part recursively

             sort(a, less, great, false);

         } else { // Partitioning with one pivot

             /*

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

              * This value is inexpensive approximation of the median.

              */

             long pivot = a[e3];

             /*

              * Partitioning degenerates to the traditional 3-way

              * (or "Dutch National Flag") schema:

              *

              *   left part    center part              right part

              * +-------------------------------------------------+

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

              * +-------------------------------------------------+

              *              ^              ^        ^

              *              |              |        |

              *             less            k      great

              *

              * Invariants:

              *

              *   all in (left, less)   < pivot

              *   all in [less, k)     == pivot

              *   all in (great, right) > pivot

              *

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

              */

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

                 if (a[k] == pivot) {

                     continue;

                 }

                 long ak = a[k];

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

                     a[k] = a[less];

                     a[less] = ak;

                     ++less;

                 } else { // a[k] > pivot - Move a[k] to right part

                     while (a[great] > pivot) {

                         --great;

                     }

                     if (a[great] < pivot) { // a[great] <= pivot

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

                     } else { // a[great] == pivot

                         /*

                          * Even though a[great] equals to pivot, the

                          * assignment a[k] = pivot may be incorrect,

                          * if a[great] and pivot are floating-point

                          * zeros of different signs. Therefore in float

                          * and double sorting methods we have to use

                          * more accurate assignment a[k] = a[great].

                          */

                         a[k] = pivot;

                     }

                     a[great] = ak;

                     --great;

                 }

             }

             /*

              * Sort left and right parts recursively.

              * All elements from center part are equal

              * and, therefore, already sorted.

              */

             sort(a, left, less - 1, leftmost);

             sort(a, great + 1, right, false);

         }

     }

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(short[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use counting sort on large arrays

         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {

             int[] count = new int[NUM_SHORT_VALUES];

             for (int i = left - 1; ++i <= right;

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

             );

             for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {

                 while (count[--i] == 0);

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

                 int s = count[i];

                 do {

                     a[--k] = value;

                 } while (--s > 0);

             }

         } else { // Use Dual-Pivot Quicksort on small arrays

             doSort(a, left, right);

         }

     }

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

     private static final int NUM_SHORT_VALUES = 1 << 16;

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

                     short t = a[lo]; a[lo] = a[hi]; a[hi] = t;

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         short[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new short[b.length];

             for (int i = left - 1; ++i < right; a[i] = b[i]);

         } else {

             b = new short[a.length];

         }

         // Merging

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

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

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

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

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

                         b[i] = a[p++];

                     } else {

                         b[i] = a[q++];

                     }

                 }

                 run[++last] = hi;

             }

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

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

                     b[i] = a[i]

                 );

                 run[++last] = right;

             }

             short[] t = a; a = b; b = t;

         }

     }

     /**

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

      *

      * @param a the array to be sorted

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

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

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

      */

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

         int length = right - left + 1;

         // Use insertion sort on tiny arrays

         if (length < INSERTION_SORT_THRESHOLD) {

             if (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort,

                  * optimized for server VM, is used in case of

                  * the leftmost part.

                  */

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

                     short ai = a[i + 1];

                     while (ai < a[j]) {

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

                         if (j-- == left) {

                             break;

                         }

                     }

                     a[j + 1] = ai;

                 }

             } else {

                 /*

                  * Skip the longest ascending sequence.

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

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

                 /*

                  * Every element from adjoining part plays the role

                  * of sentinel, therefore this allows us to avoid the

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

                  * the more optimized algorithm, so called pair insertion

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

                  * than traditional implementation of insertion sort.

                  */

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

                     short a1 = a[k], a2 = a[left];

                     if (a1 < a2) {

                         a2 = a1; a1 = a[left];

                     }

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

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

                     }

                     a[++k + 1] = a1;

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

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

                     }

                     a[k + 1] = a2;

                 }

                 short last = a[right];

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

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

                 }

                 a[right + 1] = last;

             }

             return;

         }

         // Inexpensive approximation of length / 7

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

         /*

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

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

          * pivot selection as described below. The choice for spacing

          * these elements was empirically determined to work well on

          * a wide variety of inputs.

          */

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

         int e2 = e3 - seventh;

         int e1 = e2 - seventh;

         int e4 = e3 + seventh;

         int e5 = e4 + seventh;

         // Sort these elements using insertion sort

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

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

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

         }

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

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

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

             }

         }

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

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

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

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

                 }

             }

         }

         // Pointers

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

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

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

             /*

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

              * These values are inexpensive approximations of the first and

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

              */

             short pivot1 = a[e2];

             short pivot2 = a[e4];

             /*

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

              * locations formerly occupied by the pivots. When partitioning

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

              * positions, and excluded from subsequent sorting.

              */

             a[e2] = a[left];

             a[e4] = a[right];

             /*

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

              */

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

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

             /*

              * Partitioning:

              *

              *   left part           center part                   right part

              * +--------------------------------------------------------------+

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

              * +--------------------------------------------------------------+

              *               ^                          ^       ^

              *               |                          |       |

              *              less                        k     great

              *

              * Invariants:

              *

              *              all in (left, less)   < pivot1

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

              *              all in (great, right) > pivot2

              *

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

              */

             outer:

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

                 short ak = a[k];

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

                     a[k] = a[less];

                     /*

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

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

                      */

                     a[less] = ak;

                     ++less;

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

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                             break outer;

                         }

                     }

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

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

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

                         a[k] = a[great];

                     }

                     /*

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

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

                      */

                     a[great] = ak;

                     --great;

                 }

             }

             // Swap pivots into their final positions

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

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

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

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

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

             /*

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

              * swap internal pivot values to ends.

              */

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

                 /*

                  * Skip elements, which are equal to pivot values.

                  */

                 while (a[less] == pivot1) {

                     ++less;

                 }

                 while (a[great] == pivot2) {

                     --great;

                 }

                 /*

                  * Partitioning:

                  *

                  *   left part         center part                  right part

                  * +----------------------------------------------------------+

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

                  * +----------------------------------------------------------+

                  *              ^                        ^       ^

                  *              |                        |       |

                  *             less                      k     great

                  *

                  * Invariants:

                  *

                  *              all in (*,  less) == pivot1

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

                  *              all in (great, *) == pivot2

                  *

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

                  */

                 outer:

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

                     short ak = a[k];

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

                         a[k] = a[less];

                         a[less] = ak;

                         ++less;

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

                         while (a[great] == pivot2) {

                             if (great-- == k) {

                                 break outer;

                             }

                         }

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

                             a[k] = a[less];

                             /*

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

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

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

                              * of different signs. Therefore in float and

                              * double sorting methods we have to use more

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

                              */

                             a[less] = pivot1;

                             ++less;

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

                             a[k] = a[great];

                         }

                         a[great] = ak;

                         --great;

                     }

                 }

             }

             // Sort center part recursively

             sort(a, less, great, false);

         } else { // Partitioning with one pivot

             /*

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

              * This value is inexpensive approximation of the median.

              */

             short pivot = a[e3];

             /*

              * Partitioning degenerates to the traditional 3-way

              * (or "Dutch National Flag") schema:

              *

              *   left part    center part              right part

              * +-------------------------------------------------+

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

              * +-------------------------------------------------+

              *              ^              ^        ^

              *              |              |        |

              *             less            k      great

              *

              * Invariants:

              *

              *   all in (left, less)   < pivot

              *   all in [less, k)     == pivot

              *   all in (great, right) > pivot

              *

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

              */

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

                 if (a[k] == pivot) {

                     continue;

                 }

                 short ak = a[k];

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

                     a[k] = a[less];

                     a[less] = ak;

                     ++less;

                 } else { // a[k] > pivot - Move a[k] to right part

                     while (a[great] > pivot) {

                         --great;

                     }

                     if (a[great] < pivot) { // a[great] <= pivot

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

                     } else { // a[great] == pivot

                         /*

                          * Even though a[great] equals to pivot, the

                          * assignment a[k] = pivot may be incorrect,

                          * if a[great] and pivot are floating-point

                          * zeros of different signs. Therefore in float

                          * and double sorting methods we have to use

                          * more accurate assignment a[k] = a[great].

                          */

                         a[k] = pivot;

                     }

                     a[great] = ak;

                     --great;

                 }

             }

             /*

              * Sort left and right parts recursively.

              * All elements from center part are equal

              * and, therefore, already sorted.

              */

             sort(a, left, less - 1, leftmost);

             sort(a, great + 1, right, false);

         }

     }

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(char[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use counting sort on large arrays

         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {

             int[] count = new int[NUM_CHAR_VALUES];

             for (int i = left - 1; ++i <= right;

                 count[a[i]]++

             );

             for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {

                 while (count[--i] == 0);

                 char value = (char) i;

                 int s = count[i];

                 do {

                     a[--k] = value;

                 } while (--s > 0);

             }

         } else { // Use Dual-Pivot Quicksort on small arrays

             doSort(a, left, right);

         }

     }

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

     private static final int NUM_CHAR_VALUES = 1 << 16;

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

                     char t = a[lo]; a[lo] = a[hi]; a[hi] = t;

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         char[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new char[b.length];

             for (int i = left - 1; ++i < right; a[i] = b[i]);

         } else {

             b = new char[a.length];

         }

         // Merging

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

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

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

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

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

                         b[i] = a[p++];

                     } else {

                         b[i] = a[q++];

                     }

                 }

                 run[++last] = hi;

             }

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

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

                     b[i] = a[i]

                 );

                 run[++last] = right;

             }

             char[] t = a; a = b; b = t;

         }

     }

     /**

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

      *

      * @param a the array to be sorted

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

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

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

      */

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

         int length = right - left + 1;

         // Use insertion sort on tiny arrays

         if (length < INSERTION_SORT_THRESHOLD) {

             if (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort,

                  * optimized for server VM, is used in case of

                  * the leftmost part.

                  */

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

                     char ai = a[i + 1];

                     while (ai < a[j]) {

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

                         if (j-- == left) {

                             break;

                         }

                     }

                     a[j + 1] = ai;

                 }

             } else {

                 /*

                  * Skip the longest ascending sequence.

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

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

                 /*

                  * Every element from adjoining part plays the role

                  * of sentinel, therefore this allows us to avoid the

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

                  * the more optimized algorithm, so called pair insertion

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

                  * than traditional implementation of insertion sort.

                  */

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

                     char a1 = a[k], a2 = a[left];

                     if (a1 < a2) {

                         a2 = a1; a1 = a[left];

                     }

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

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

                     }

                     a[++k + 1] = a1;

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

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

                     }

                     a[k + 1] = a2;

                 }

                 char last = a[right];

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

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

                 }

                 a[right + 1] = last;

             }

             return;

         }

         // Inexpensive approximation of length / 7

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

         /*

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

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

          * pivot selection as described below. The choice for spacing

          * these elements was empirically determined to work well on

          * a wide variety of inputs.

          */

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

         int e2 = e3 - seventh;

         int e1 = e2 - seventh;

         int e4 = e3 + seventh;

         int e5 = e4 + seventh;

         // Sort these elements using insertion sort

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

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

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

         }

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

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

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

             }

         }

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

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

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

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

                 }

             }

         }

         // Pointers

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

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

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

             /*

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

              * These values are inexpensive approximations of the first and

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

              */

             char pivot1 = a[e2];

             char pivot2 = a[e4];

             /*

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

              * locations formerly occupied by the pivots. When partitioning

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

              * positions, and excluded from subsequent sorting.

              */

             a[e2] = a[left];

             a[e4] = a[right];

             /*

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

              */

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

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

             /*

              * Partitioning:

              *

              *   left part           center part                   right part

              * +--------------------------------------------------------------+

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

              * +--------------------------------------------------------------+

              *               ^                          ^       ^

              *               |                          |       |

              *              less                        k     great

              *

              * Invariants:

              *

              *              all in (left, less)   < pivot1

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

              *              all in (great, right) > pivot2

              *

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

              */

             outer:

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

                 char ak = a[k];

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

                     a[k] = a[less];

                     /*

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

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

                      */

                     a[less] = ak;

                     ++less;

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

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                             break outer;

                         }

                     }

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

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

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

                         a[k] = a[great];

                     }

                     /*

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

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

                      */

                     a[great] = ak;

                     --great;

                 }

             }

             // Swap pivots into their final positions

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

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

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

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

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

             /*

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

              * swap internal pivot values to ends.

              */

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

                 /*

                  * Skip elements, which are equal to pivot values.

                  */

                 while (a[less] == pivot1) {

                     ++less;

                 }

                 while (a[great] == pivot2) {

                     --great;

                 }

                 /*

                  * Partitioning:

                  *

                  *   left part         center part                  right part

                  * +----------------------------------------------------------+

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

                  * +----------------------------------------------------------+

                  *              ^                        ^       ^

                  *              |                        |       |

                  *             less                      k     great

                  *

                  * Invariants:

                  *

                  *              all in (*,  less) == pivot1

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

                  *              all in (great, *) == pivot2

                  *

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

                  */

                 outer:

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

                     char ak = a[k];

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

                         a[k] = a[less];

                         a[less] = ak;

                         ++less;

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

                         while (a[great] == pivot2) {

                             if (great-- == k) {

                                 break outer;

                             }

                         }

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

                             a[k] = a[less];

                             /*

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

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

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

                              * of different signs. Therefore in float and

                              * double sorting methods we have to use more

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

                              */

                             a[less] = pivot1;

                             ++less;

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

                             a[k] = a[great];

                         }

                         a[great] = ak;

                         --great;

                     }

                 }

             }

             // Sort center part recursively

             sort(a, less, great, false);

         } else { // Partitioning with one pivot

             /*

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

              * This value is inexpensive approximation of the median.

              */

             char pivot = a[e3];

             /*

              * Partitioning degenerates to the traditional 3-way

              * (or "Dutch National Flag") schema:

              *

              *   left part    center part              right part

              * +-------------------------------------------------+

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

              * +-------------------------------------------------+

              *              ^              ^        ^

              *              |              |        |

              *             less            k      great

              *

              * Invariants:

              *

              *   all in (left, less)   < pivot

              *   all in [less, k)     == pivot

              *   all in (great, right) > pivot

              *

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

              */

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

                 if (a[k] == pivot) {

                     continue;

                 }

                 char ak = a[k];

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

                     a[k] = a[less];

                     a[less] = ak;

                     ++less;

                 } else { // a[k] > pivot - Move a[k] to right part

                     while (a[great] > pivot) {

                         --great;

                     }

                     if (a[great] < pivot) { // a[great] <= pivot

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

                     } else { // a[great] == pivot

                         /*

                          * Even though a[great] equals to pivot, the

                          * assignment a[k] = pivot may be incorrect,

                          * if a[great] and pivot are floating-point

                          * zeros of different signs. Therefore in float

                          * and double sorting methods we have to use

                          * more accurate assignment a[k] = a[great].

                          */

                         a[k] = pivot;

                     }

                     a[great] = ak;

                     --great;

                 }

             }

             /*

              * Sort left and right parts recursively.

              * All elements from center part are equal

              * and, therefore, already sorted.

              */

             sort(a, left, less - 1, leftmost);

             sort(a, great + 1, right, false);

         }

     }

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

     private static final int NUM_BYTE_VALUES = 1 << 8;

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(byte[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         // Use counting sort on large arrays

         if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {

             int[] count = new int[NUM_BYTE_VALUES];

             for (int i = left - 1; ++i <= right;

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

             );

             for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {

                 while (count[--i] == 0);

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

                 int s = count[i];

                 do {

                     a[--k] = value;

                 } while (--s > 0);

             }

         } else { // Use insertion sort on small arrays

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

                 byte ai = a[i + 1];

                 while (ai < a[j]) {

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

                     if (j-- == left) {

                         break;

                     }

                 }

                 a[j + 1] = ai;

             }

         }

     }

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(float[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         /*

          * Phase 1: Move NaNs to the end of the array.

          */

         while (left <= right && Float.isNaN(a[right])) {

             --right;

         }

         for (int k = right; --k >= left; ) {

             float ak = a[k];

             if (ak != ak) { // a[k] is NaN

                 a[k] = a[right];

                 a[right] = ak;

                 --right;

             }

         }

         /*

          * Phase 2: Sort everything except NaNs (which are already in place).

          */

         doSort(a, left, right);

         /*

          * Phase 3: Place negative zeros before positive zeros.

          */

         int hi = right;

         /*

          * Find the first zero, or first positive, or last negative element.

          */

         while (left < hi) {

             int middle = (left + hi) >>> 1;

             float middleValue = a[middle];

             if (middleValue < 0.0f) {

                 left = middle + 1;

             } else {

                 hi = middle;

             }

         }

         /*

          * Skip the last negative value (if any) or all leading negative zeros.

          */

         while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {

             ++left;

         }

         /*

          * Move negative zeros to the beginning of the sub-range.

          *

          * Partitioning:

          *

          * +----------------------------------------------------+

          * |   < 0.0   |   -0.0   |   0.0   |   ?  ( >= 0.0 )   |

          * +----------------------------------------------------+

          *              ^          ^         ^

          *              |          |         |

          *             left        p         k

          *

          * Invariants:

          *

          *   all in (*,  left)  <  0.0

          *   all in [left,  p) == -0.0

          *   all in [p,     k) ==  0.0

          *   all in [k, right] >=  0.0

          *

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

          */

         for (int k = left, p = left - 1; ++k <= right; ) {

             float ak = a[k];

             if (ak != 0.0f) {

                 break;

             }

             if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f

                 a[k] = 0.0f;

                 a[++p] = -0.0f;

             }

         }

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

     private static void doSort(float[] a, int left, int right) {

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

                     float t = a[lo]; a[lo] = a[hi]; a[hi] = t;

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         float[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new float[b.length];

             for (int i = left - 1; ++i < right; a[i] = b[i]);

         } else {

             b = new float[a.length];

         }

         // Merging

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

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

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

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

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

                         b[i] = a[p++];

                     } else {

                         b[i] = a[q++];

                     }

                 }

                 run[++last] = hi;

             }

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

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

                     b[i] = a[i]

                 );

                 run[++last] = right;

             }

             float[] t = a; a = b; b = t;

         }

     }

     /**

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

      *

      * @param a the array to be sorted

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

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

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

      */

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

         int length = right - left + 1;

         // Use insertion sort on tiny arrays

         if (length < INSERTION_SORT_THRESHOLD) {

             if (leftmost) {

                 /*

                  * Traditional (without sentinel) insertion sort,

                  * optimized for server VM, is used in case of

                  * the leftmost part.

                  */

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

                     float ai = a[i + 1];

                     while (ai < a[j]) {

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

                         if (j-- == left) {

                             break;

                         }

                     }

                     a[j + 1] = ai;

                 }

             } else {

                 /*

                  * Skip the longest ascending sequence.

                  */

                 do {

                     if (left >= right) {

                         return;

                     }

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

                 /*

                  * Every element from adjoining part plays the role

                  * of sentinel, therefore this allows us to avoid the

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

                  * the more optimized algorithm, so called pair insertion

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

                  * than traditional implementation of insertion sort.

                  */

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

                     float a1 = a[k], a2 = a[left];

                     if (a1 < a2) {

                         a2 = a1; a1 = a[left];

                     }

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

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

                     }

                     a[++k + 1] = a1;

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

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

                     }

                     a[k + 1] = a2;

                 }

                 float last = a[right];

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

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

                 }

                 a[right + 1] = last;

             }

             return;

         }

         // Inexpensive approximation of length / 7

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

         /*

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

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

          * pivot selection as described below. The choice for spacing

          * these elements was empirically determined to work well on

          * a wide variety of inputs.

          */

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

         int e2 = e3 - seventh;

         int e1 = e2 - seventh;

         int e4 = e3 + seventh;

         int e5 = e4 + seventh;

         // Sort these elements using insertion sort

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

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

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

         }

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

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

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

             }

         }

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

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

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

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

                 }

             }

         }

         // Pointers

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

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

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

             /*

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

              * These values are inexpensive approximations of the first and

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

              */

             float pivot1 = a[e2];

             float pivot2 = a[e4];

             /*

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

              * locations formerly occupied by the pivots. When partitioning

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

              * positions, and excluded from subsequent sorting.

              */

             a[e2] = a[left];

             a[e4] = a[right];

             /*

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

              */

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

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

             /*

              * Partitioning:

              *

              *   left part           center part                   right part

              * +--------------------------------------------------------------+

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

              * +--------------------------------------------------------------+

              *               ^                          ^       ^

              *               |                          |       |

              *              less                        k     great

              *

              * Invariants:

              *

              *              all in (left, less)   < pivot1

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

              *              all in (great, right) > pivot2

              *

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

              */

             outer:

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

                 float ak = a[k];

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

                     a[k] = a[less];

                     /*

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

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

                      */

                     a[less] = ak;

                     ++less;

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

                     while (a[great] > pivot2) {

                         if (great-- == k) {

                             break outer;

                         }

                     }

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

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

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

                         a[k] = a[great];

                     }

                     /*

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

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

                      */

                     a[great] = ak;

                     --great;

                 }

             }

             // Swap pivots into their final positions

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

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

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

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

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

             /*

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

              * swap internal pivot values to ends.

              */

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

                 /*

                  * Skip elements, which are equal to pivot values.

                  */

                 while (a[less] == pivot1) {

                     ++less;

                 }

                 while (a[great] == pivot2) {

                     --great;

                 }

                 /*

                  * Partitioning:

                  *

                  *   left part         center part                  right part

                  * +----------------------------------------------------------+

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

                  * +----------------------------------------------------------+

                  *              ^                        ^       ^

                  *              |                        |       |

                  *             less                      k     great

                  *

                  * Invariants:

                  *

                  *              all in (*,  less) == pivot1

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

                  *              all in (great, *) == pivot2

                  *

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

                  */

                 outer:

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

                     float ak = a[k];

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

                         a[k] = a[less];

                         a[less] = ak;

                         ++less;

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

                         while (a[great] == pivot2) {

                             if (great-- == k) {

                                 break outer;

                             }

                         }

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

                             a[k] = a[less];

                             /*

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

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

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

                              * of different signs. Therefore in float and

                              * double sorting methods we have to use more

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

                              */

                             a[less] = a[great];

                             ++less;

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

                             a[k] = a[great];

                         }

                         a[great] = ak;

                         --great;

                     }

                 }

             }

             // Sort center part recursively

             sort(a, less, great, false);

         } else { // Partitioning with one pivot

             /*

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

              * This value is inexpensive approximation of the median.

              */

             float pivot = a[e3];

             /*

              * Partitioning degenerates to the traditional 3-way

              * (or "Dutch National Flag") schema:

              *

              *   left part    center part              right part

              * +-------------------------------------------------+

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

              * +-------------------------------------------------+

              *              ^              ^        ^

              *              |              |        |

              *             less            k      great

              *

              * Invariants:

              *

              *   all in (left, less)   < pivot

              *   all in [less, k)     == pivot

              *   all in (great, right) > pivot

              *

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

              */

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

                 if (a[k] == pivot) {

                     continue;

                 }

                 float ak = a[k];

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

                     a[k] = a[less];

                     a[less] = ak;

                     ++less;

                 } else { // a[k] > pivot - Move a[k] to right part

                     while (a[great] > pivot) {

                         --great;

                     }

                     if (a[great] < pivot) { // a[great] <= pivot

                         a[k] = a[less];

                         a[less] = a[great];

                         ++less;

                     } else { // a[great] == pivot

                         /*

                          * Even though a[great] equals to pivot, the

                          * assignment a[k] = pivot may be incorrect,

                          * if a[great] and pivot are floating-point

                          * zeros of different signs. Therefore in float

                          * and double sorting methods we have to use

                          * more accurate assignment a[k] = a[great].

                          */

                         a[k] = a[great];

                     }

                     a[great] = ak;

                     --great;

                 }

             }

             /*

              * Sort left and right parts recursively.

              * All elements from center part are equal

              * and, therefore, already sorted.

              */

             sort(a, left, less - 1, leftmost);

             sort(a, great + 1, right, false);

         }

     }

     /**

      * Sorts the specified array.

      *

      * @param a the array to be sorted

      */

     public static void sort(double[] a) {

         sort(a, 0, a.length - 1);

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

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

         /*

          * Phase 1: Move NaNs to the end of the array.

          */

         while (left <= right && Double.isNaN(a[right])) {

             --right;

         }

         for (int k = right; --k >= left; ) {

             double ak = a[k];

             if (ak != ak) { // a[k] is NaN

                 a[k] = a[right];

                 a[right] = ak;

                 --right;

             }

         }

         /*

          * Phase 2: Sort everything except NaNs (which are already in place).

          */

         doSort(a, left, right);

         /*

          * Phase 3: Place negative zeros before positive zeros.

          */

         int hi = right;

         /*

          * Find the first zero, or first positive, or last negative element.

          */

         while (left < hi) {

             int middle = (left + hi) >>> 1;

             double middleValue = a[middle];

             if (middleValue < 0.0d) {

                 left = middle + 1;

             } else {

                 hi = middle;

             }

         }

         /*

          * Skip the last negative value (if any) or all leading negative zeros.

          */

         while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {

             ++left;

         }

         /*

          * Move negative zeros to the beginning of the sub-range.

          *

          * Partitioning:

          *

          * +----------------------------------------------------+

          * |   < 0.0   |   -0.0   |   0.0   |   ?  ( >= 0.0 )   |

          * +----------------------------------------------------+

          *              ^          ^         ^

          *              |          |         |

          *             left        p         k

          *

          * Invariants:

          *

          *   all in (*,  left)  <  0.0

          *   all in [left,  p) == -0.0

          *   all in [p,     k) ==  0.0

          *   all in [k, right] >=  0.0

          *

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

          */

         for (int k = left, p = left - 1; ++k <= right; ) {

             double ak = a[k];

             if (ak != 0.0d) {

                 break;

             }

             if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d

                 a[k] = 0.0d;

                 a[++p] = -0.0d;

             }

         }

     }

     /**

      * Sorts the specified range of the array.

      *

      * @param a the array to be sorted

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

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

      */

     private static void doSort(double[] a, int left, int right) {

         // Use Quicksort on small arrays

         if (right - left < QUICKSORT_THRESHOLD) {

             sort(a, left, right, true);

             return;

         }

         /*

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

          * (ascending or descending sequence).

          */

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

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

         // Check if the array is nearly sorted

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

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

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

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

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

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

                     double t = a[lo]; a[lo] = a[hi]; a[hi] = t;

                 }

             } else { // equal

                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {

                     if (--m == 0) {

                         sort(a, left, right, true);

                         return;

                     }

                 }

             }

             /*

              * The array is not highly structured,

              * use Quicksort instead of merge sort.

              */

             if (++count == MAX_RUN_COUNT) {

                 sort(a, left, right, true);

                 return;

             }

         }

         // Check special cases

         if (run[count] == right++) { // The last run contains one element

             run[++count] = right;

         } else if (count == 1) { // The array is already sorted

             return;

         }

         /*

          * Create temporary array, which is used for merging.

          * Implementation note: variable "right" is increased by 1.

          */

         double[] b; byte odd = 0;

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

         if (odd == 0) {

             b = a; a = new double[b.length];