Class Outline

/* 
 * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved. 
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 */ 
 
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. 
 * 
 * All exposed methods are package-private, designed to be invoked 
 * from public methods (in class Arrays) after performing any 
 * necessary array bounds checks and expanding parameters into the 
 * required forms. 
 * 
 * @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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(int[] a, int left, int right, 
                     int[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        int[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new int[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            int[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(long[] a, int left, int right, 
                     long[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        long[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new long[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            long[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(short[] a, int left, int right, 
                     short[] work, int workBase, int workLen) { 
        // 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, work, workBase, workLen); 
        } 
    } 
 
    /** 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 
     * @param work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    private static void doSort(short[] a, int left, int right, 
                               short[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        short[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new short[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            short[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(char[] a, int left, int right, 
                     char[] work, int workBase, int workLen) { 
        // 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, work, workBase, workLen); 
        } 
    } 
 
    /** 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 
     * @param work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    private static void doSort(char[] a, int left, int right, 
                               char[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        char[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new char[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            char[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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 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 
     */ 
    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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(float[] a, int left, int right, 
                     float[] work, int workBase, int workLen) { 
        /* 
         * 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, work, workBase, workLen); 
 
        /* 
         * 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 
     * @param work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    private static void doSort(float[] a, int left, int right, 
                               float[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        float[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new float[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            float[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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 range of the array using the given 
     * workspace array slice if possible for merging 
     * 
     * @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 work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    static void sort(double[] a, int left, int right, 
                     double[] work, int workBase, int workLen) { 
        /* 
         * 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, work, workBase, workLen); 
 
        /* 
         * 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 
     * @param work a workspace array (slice) 
     * @param workBase origin of usable space in work array 
     * @param workLen usable size of work array 
     */ 
    private static void doSort(double[] a, int left, int right, 
                               double[] work, int workBase, int workLen) { 
        // 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 
        // Implementation note: variable "right" is increased by 1. 
        if (run[count] == right++) { // The last run contains one element 
            run[++count] = right; 
        } else if (count == 1) { // The array is already sorted 
            return; 
        } 
 
        // Determine alternation base for merge 
        byte odd = 0; 
        for (int n = 1; (n <<= 1) < count; odd ^= 1); 
 
        // Use or create temporary array b for merging 
        double[] b;                 // temp array; alternates with a 
        int ao, bo;              // array offsets from 'left' 
        int blen = right - left; // space needed for b 
        if (work == null || workLen < blen || workBase + blen > work.length) { 
            work = new double[blen]; 
            workBase = 0; 
        } 
        if (odd == 0) { 
            System.arraycopy(a, left, work, workBase, blen); 
            b = a; 
            bo = 0; 
            a = work; 
            ao = workBase - left; 
        } else { 
            b = work; 
            ao = 0; 
            bo = workBase - left; 
        } 
 
        // 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 + ao] <= a[q + ao]) { 
                        b[i + bo] = a[p++ + ao]; 
                    } else { 
                        b[i + bo] = a[q++ + ao]; 
                    } 
                } 
                run[++last] = hi; 
            } 
            if ((count & 1) != 0) { 
                for (int i = right, lo = run[count - 1]; --i >= lo; 
                    b[i + bo] = a[i + ao] 
                ); 
                run[++last] = right; 
            } 
            double[] t = a; a = b; b = t; 
            int o = ao; ao = bo; bo = o; 
        } 
    } 
 
    /** 
     * 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(double[] 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) { 
                    double 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) { 
                    double 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; 
                } 
                double 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]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; } 
 
        if (a[e3] < a[e2]) { double 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]) { double 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]) { double 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. 
             */ 
            double pivot1 = a[e2]; 
            double 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; ) { 
                double 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; ) { 
                    double 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. 
             */ 
            double 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; 
                } 
                double 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); 
        } 
    } 
}