/*
 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation. Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package java.util;

import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveAction;

/**
 * This class implements powerful and fully optimized versions, both
 * sequential and parallel, of the Dual-Pivot Quicksort algorithm by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 *
 * @version 2018.02.18
 * @since 1.7
 */
final class DualPivotQuicksort {

    /**
     * Prevents instantiation.
     */
    private DualPivotQuicksort() {}

    /**
     * If the length of the leftmost part to be sorted is less than
     * this constant, heap sort is used in preference to Quicksort.
     */
    private static final int HEAP_SORT_THRESHOLD = 69;

    /**
     * If the length of non-leftmost part to be sorted is less than this
     * constant, nano insertion sort is used in preference to Quicksort.
     */
    private static final int NANO_INSERTION_SORT_THRESHOLD = 36;

    /**
     * If the length of non-leftmost part to be sorted is less than this
     * constant, pair insertion sort is used in preference to Quicksort.
     */
    private static final int PAIR_INSERTION_SORT_THRESHOLD = 88;

    /**
     * The minimal length of an array, required by parallel Quicksort.
     */
    private static final int PARALLEL_QUICKSORT_THRESHOLD = 1024;

    /**
     * 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 = 41;

    /**
     * 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 = 2180;

    /**
     * if the depth of the Quicksort recursion exceeds this
     * constant, heap sort is used in preference to Quicksort.
     */
    private static final int MAX_RECURSION_DEPTH = 100;

    /**
     * This constant is combination of maximum Quicksort recursion depth
     * and binary flag, where the right bit "0" indicates that the whole
     * array is considered as the leftmost part.
     */
    private static final int LEFTMOST_BITS = MAX_RECURSION_DEPTH << 1;

    /**
     * This class implements the parallel Dual-Pivot Quicksort.
     */
    @SuppressWarnings("serial")
    private static class Sorter<T> extends RecursiveAction {

        Sorter(T a, int bits, int low, int high) {
            this.a = a;
            this.bits = bits;
            this.low = low;
            this.high = high;
        }

        @Override
        protected void compute() {
            Class<?> clazz = a.getClass();

            if (clazz == int[].class) {
                sort((int[]) a, bits, true, low, high);
            } else if (clazz == long[].class) {
                sort((long[]) a, bits, true, low, high);
            } else if (clazz == char[].class) {
                sort((char[]) a, bits, true, low, high);
            } else if (clazz == short[].class) {
                sort((short[]) a, bits, true, low, high);
            } else if (clazz == float[].class) {
                sort((float[]) a, bits, true, low, high);
            } else if (clazz == double[].class) {
                sort((double[]) a, bits, true, low, high);
            } else {
                throw new IllegalArgumentException(
                    "Unknown type of array: " + clazz.getName());
            }
        }

        private T a;
        private int bits;
        private int low;
        private int high;
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(int[] a, boolean parallel, int low, int high) {
        sort(a, LEFTMOST_BITS, parallel, low, high);
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(int[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { int t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            int pivot1 = a[e1];
            int pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                int ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<int[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<int[]>(a, bits | 1, upper + 1, high),
                    new Sorter<int[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            int pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                int ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<int[]>(a, bits, low, lower),
                    new Sorter<int[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(long[] a, boolean parallel, int low, int high) {
        sort(a, LEFTMOST_BITS, parallel, low, high);
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(long[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { long t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { long t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            long pivot1 = a[e1];
            long pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                long ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<long[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<long[]>(a, bits | 1, upper + 1, high),
                    new Sorter<long[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            long pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                long ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<long[]>(a, bits, low, lower),
                    new Sorter<long[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(byte[] a, boolean parallel, int low, int high) {
        if (high - low > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
            SortingAlgorithms.countingSort(a, low, high);
        } else {
            SortingAlgorithms.insertionSort(a, low, high);
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(char[] a, boolean parallel, int low, int high) {
        if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
            SortingAlgorithms.countingSort(a, low, high);
        } else {
            sort(a, LEFTMOST_BITS, parallel, low, high);
        }
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(char[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { char t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { char t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            char pivot1 = a[e1];
            char pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                char ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<char[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<char[]>(a, bits | 1, upper + 1, high),
                    new Sorter<char[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            char pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                char ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<char[]>(a, bits, low, lower),
                    new Sorter<char[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(short[] a, boolean parallel, int low, int high) {
        if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
            SortingAlgorithms.countingSort(a, low, high);
        } else {
            sort(a, LEFTMOST_BITS, parallel, low, high);
        }
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(short[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { short t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { short t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            short pivot1 = a[e1];
            short pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                short ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<short[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<short[]>(a, bits | 1, upper + 1, high),
                    new Sorter<short[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            short pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                short ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<short[]>(a, bits, low, lower),
                    new Sorter<short[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(float[] a, boolean parallel, int low, int high) {
        /*
         * Phase 1. Count the number of negative zero -0.0f,
         * turn them into positive zero, and move all NaNs
         * to the end of the array.
         */
        int numNegativeZero = 0;

        for (int k = high; k > low; ) {
            float ak = a[--k];

            if (ak == 0.0f && Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
                numNegativeZero += 1;
                a[k] = 0.0f;
            } else if (ak != ak) { // ak is NaN
                a[k] = a[--high];
                a[high] = ak;
            }
        }

        /*
         * Phase 2. Sort everything except NaNs,
         * which are already in place.
         */
        sort(a, LEFTMOST_BITS, parallel, low, high);

        /*
         * Phase 3. Turn positive zero 0.0f
         * back into negative zero -0.0f.
         */
        if (++numNegativeZero == 1) {
            return;
        }

        /*
         * Find the position one less than
         * the index of the first zero.
         */
        while (low <= high) {
            int middle = (low + high) >>> 1;

            if (a[middle] < 0) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        /*
         * Replace the required number of 0.0f by -0.0f.
         */
        while (--numNegativeZero > 0) {
            a[++high] = -0.0f;
        }
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(float[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { float t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { float t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { float t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            float pivot1 = a[e1];
            float pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                float ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<float[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<float[]>(a, bits | 1, upper + 1, high),
                    new Sorter<float[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            float pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                float ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<float[]>(a, bits, low, lower),
                    new Sorter<float[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }

    /**
     * Sorts the specified range of the array.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(double[] a, boolean parallel, int low, int high) {
        /*
         * Phase 1. Count the number of negative zero -0.0d,
         * turn them into positive zero, and move all NaNs
         * to the end of the array.
         */
        int numNegativeZero = 0;

        for (int k = high; k > low; ) {
            double ak = a[--k];

            if (ak == 0.0d && Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
                numNegativeZero += 1;
                a[k] = 0.0d;
            } else if (ak != ak) { // ak is NaN
                a[k] = a[--high];
                a[high] = ak;
            }
        }

        /*
         * Phase 2. Sort everything except NaNs,
         * which are already in place.
         */
        sort(a, LEFTMOST_BITS, parallel, low, high);

        /*
         * Phase 3. Turn positive zero 0.0d
         * back into negative zero -0.0d.
         */
        if (++numNegativeZero == 1) {
            return;
        }

        /*
         * Find the position one less than
         * the index of the first zero.
         */
        while (low <= high) {
            int middle = (low + high) >>> 1;

            if (a[middle] < 0) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        /*
         * Replace the required number of 0.0d by -0.0d.
         */
        while (--numNegativeZero > 0) {
            a[++high] = -0.0d;
        }
    }

    /**
     * Sorts the specified range of the array by the Dual-Pivot Quicksort.
     *
     * @param a the array to be sorted
     * @param bits the recursion depth of Quicksort and the leftmost flag
     * @param parallel indicates whether sorting is performed in parallel
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    private static void sort(double[] a, int bits, boolean parallel, int low, int high) {
        int end = high - 1, length = high - low;

        /*
         * Run insertion sorts on non-leftmost part.
         */
        if ((bits & 1) > 0) {

            /*
             * Use nano insertion sort on tiny part.
             */
            if (length < NANO_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.nanoInsertionSort(a, low, high);
                return;
            }

            /*
             * Use pair insertion sort on small part.
             */
            if (length < PAIR_INSERTION_SORT_THRESHOLD) {
                SortingAlgorithms.pairInsertionSort(a, low, end);
                return;
            }
        }

        /*
         * Switch to heap sort on the leftmost part or
         * if the execution time is becoming quadratic.
         */
        if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) {
            SortingAlgorithms.heapSort(a, low, end);
            return;
        }

        /*
         * Check if the array is nearly sorted
         * and then try to sort it by Merging sort.
         */
        if (SortingAlgorithms.mergingSort(a, parallel, low, high)) {
            return;
        }

        /*
         * The splitting of the array, defined by the following
         * step, is related to the inexpensive approximation of
         * the golden ratio.
         */
        int step = (length >> 3) * 3 + 3;

        /*
         * Five elements around (and including) the central element in
         * the array will be used for pivot selection as described below.
         * The unequal choice of spacing these elements was empirically
         * determined to work well on a wide variety of inputs.
         */
        int e1 = low + step;
        int e5 = end - step;
        int e3 = (e1 + e5) >>> 1;
        int e2 = (e1 + e3) >>> 1;
        int e4 = (e3 + e5) >>> 1;

        /*
         * Sort these elements in place by the combination
         * of 5-element sorting network and insertion sort.
         */
        if (a[e5] < a[e3]) { double t = a[e5]; a[e5] = a[e3]; a[e3] = t; }
        if (a[e4] < a[e2]) { double t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
        if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
        if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t; }
        if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t; }

        if (a[e1] > a[e2]) { double t = a[e1]; a[e1] = a[e2]; a[e2] = t;
            if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t;
                if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t;
                    if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; }
                }
            }
        }

        // Pointers
        int lower = low; // The index of the last element of the left part
        int upper = end; // The index of the first element of the right part

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

            /*
             * Use the first and the fifth elements as the pivots.
             * These values are inexpensive approximation of tertiles.
             * Note, that pivot1 < pivot2.
             */
            double pivot1 = a[e1];
            double pivot2 = a[e5];

            /*
             * The first and the last elements to be sorted are moved to the
             * locations formerly occupied by the pivots. When partitioning
             * is completed, the pivots are swapped back into their final
             * positions, and excluded from subsequent sorting.
             */
            a[e1] = a[lower];
            a[e5] = a[upper];

            /*
             * Skip elements, which are less or greater than the pivots.
             */
            while (a[++lower] < pivot1);
            while (a[--upper] > pivot2);

            /*
             * Backwards 3-interval partitioning
             *
             *   left part                 central part          right part
             * +------------------------------------------------------------+
             * |  < pivot1  |   ?   |  pivot1 <= && <= pivot2  |  > pivot2  |
             * +------------------------------------------------------------+
             *             ^       ^                            ^
             *             |       |                            |
             *           lower     k                          upper
             *
             * Invariants:
             *
             *              all in (low, lower] < pivot1
             *    pivot1 <= all in (k, upper)  <= pivot2
             *              all in [upper, end) > pivot2
             *
             * Pointer k is the last index of ?-part
             */
            for (int $ = --lower, k = ++upper; --k > lower; ) {
                double ak = a[k];

                if (ak < pivot1) { // Move a[k] to the left side
                    while (a[++lower] < pivot1);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    if (a[lower] > pivot2) { // a[lower] >= pivot1
                        a[k] = a[--upper];
                        a[upper] = a[lower];
                    } else { // pivot1 <= a[lower] <= pivot2
                        a[k] = a[lower];
                    }
                    a[lower] = ak;
                } else if (ak > pivot2) { // Move a[k] to the right side
                    a[k] = a[--upper];
                    a[upper] = ak;
                }
            }

            /*
             * Swap the pivots into their final positions.
             */
            a[low] = a[lower]; a[lower] = pivot1;
            a[end] = a[upper]; a[upper] = pivot2;

            /*
             * Sort all parts recursively, excluding known pivots.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<double[]>(a, bits | 1, lower + 1, upper),
                    new Sorter<double[]>(a, bits | 1, upper + 1, high),
                    new Sorter<double[]>(a, bits, low, lower)
                );
            } else {
                sort(a, bits | 1, false, upper + 1, high);
                sort(a, bits, false, low, lower);
                sort(a, bits | 1, false, lower + 1, upper);
            }
        } else { // Partitioning with one pivot

            /*
             * Use the third element as the pivot. This value
             * is inexpensive approximation of the median.
             */
            double pivot = a[e3];

            /*
             * The first element to be sorted is moved to the location
             * formerly occupied by the pivot. When partitioning is
             * completed, the pivot is swapped back into its final
             * position, and excluded from subsequent sorting.
             */
            a[e3] = a[lower];

            /*
             * Traditional 3-way (Dutch National Flag) partitioning
             *
             *   left part                 central part    right part
             * +------------------------------------------------------+
             * |   < pivot   |     ?     |   == pivot   |   > pivot   |
             * +------------------------------------------------------+
             *              ^           ^                ^
             *              |           |                |
             *            lower         k              upper
             *
             * Invariants:
             *
             *   all in (low, lower] < pivot
             *   all in (k, upper)  == pivot
             *   all in [upper, end] > pivot
             *
             * Pointer k is the last index of ?-part
             */
            for (int k = ++upper; --k > lower; ) {
                if (a[k] == pivot) {
                    continue;
                }
                double ak = a[k];

                if (ak < pivot) { // Move a[k] to the left side
                    while (a[++lower] < pivot);

                    if (lower > k) {
                        lower = k;
                        break;
                    }
                    a[k] = pivot;

                    if (a[lower] > pivot) {
                        a[--upper] = a[lower];
                    }
                    a[lower] = ak;
                } else { // ak > pivot - Move a[k] to the right side
                    a[k] = pivot;
                    a[--upper] = ak;
                }
            }

            /*
             * Swap the pivot into its final position.
             */
            a[low] = a[lower]; a[lower] = pivot;

            /*
             * Sort the left and the right parts recursively, excluding
             * known pivot. All elements from the central part are equal
             * and, therefore, already sorted.
             */
            if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) {
                ForkJoinTask.invokeAll(
                    new Sorter<double[]>(a, bits, low, lower),
                    new Sorter<double[]>(a, bits | 1, upper, high)
                );
            } else {
                sort(a, bits | 1, false, upper, high);
                sort(a, bits, false, low, lower);
            }
        }
    }
}