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

import java.util.concurrent.CountedCompleter;

import java.util.concurrent.RecursiveTask;

 * 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

 * There are also additional algorithms, invoked from the Dual-Pivot

 * Quicksort, such as mixed insertion sort, merging of runs and heap

 * sort, counting sort and parallel merge sort.

 * @author Doug Lea

 * @version 2018.08.18

 *

 * @since 1.7 * 14

    /**

     * Max array size to use mixed insertion sort.

     */

    private static final int MAX_MIXED_INSERTION_SORT_SIZE = 65;

    /**

     * Max array size to use insertion sort.

    private static final int MAX_INSERTION_SORT_SIZE = 44;

    /**

     * Min array size to perform sorting in parallel.

     */

    private static final int MIN_PARALLEL_SORT_SIZE = 4 << 10;

    /**

     * Min array size to try merging of runs.

     */

    private static final int MIN_TRY_MERGE_SIZE = 4 << 10;

     * Min size of the first run to continue with scanning.

    private static final int MIN_FIRST_RUN_SIZE = 16;

    /**

     * Min factor for the first runs to continue scanning.

     */

    private static final int MIN_FIRST_RUNS_FACTOR = 7;

     * Max capacity of the index array for tracking runs.

     */

    private static final int MAX_RUN_CAPACITY = 5 << 10;

    /**

     * Min number of runs, required by parallel merging.

    private static final int MIN_RUN_COUNT = 4;

    /**

     * Min array size to use parallel merging of parts.

     */

    private static final int MIN_PARALLEL_MERGE_PARTS_SIZE = 4 << 10;

     * Min size of a byte array to use counting sort.

    private static final int MIN_BYTE_COUNTING_SORT_SIZE = 64;

     * Min size of a short or char array to use counting sort.

     */

    private static final int MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE = 1750;

    /**

     * Threshold of mixed insertion sort is incremented by this value.

    private static final int DELTA = 3 << 1;

    /**

     * Max recursive partitioning depth before using heap sort.

     */

    private static final int MAX_RECURSION_DEPTH = 64 * DELTA;

     * Calculates the double depth of parallel merging.

     * Depth is negative, if tasks split before sorting.

     *

     * @param parallelism the parallelism level

     * @param size the target size

     * @return the depth of parallel merging

    private static int getDepth(int parallelism, int size) {

        int depth = 0;

        while ((parallelism >>= 3) > 0 && (size >>= 2) > 0) {

            depth -= 2;

        }

        return depth;

    }

     * Sorts the specified range of the array using parallel merge

     * sort and/or Dual-Pivot Quicksort.

     *

     * To balance the faster splitting and parallelism of merge sort

     * with the faster element partitioning of Quicksort, ranges are

     * subdivided in tiers such that, if there is enough parallelism,

     * the four-way parallel merge is started, still ensuring enough

     * parallelism to process the partitions.

     * @param parallelism the parallelism level

     * @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, int parallelism, int low, int high) {

        int size = high - low;

        if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {

            int depth = getDepth(parallelism, size >> 12);

            int[] b = depth == 0 ? null : new int[size];

            new Sorter(null, a, b, low, size, low, depth).invoke();

        } else {

            sort(null, a, 0, low, high);

    }

    /**

     * Sorts the specified array using the Dual-Pivot Quicksort and/or

     * other sorts in special-cases, possibly with parallel partitions.

     *

     * @param sorter parallel context

     * @param a the array to be sorted

     * @param bits the combination of recursion depth and bit flag, where

     *        the right bit "0" indicates that array is the leftmost part

     * @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(Sorter sorter, int[] a, int bits, int low, int high) {

        while (true) {

            int end = high - 1, size = high - low;

            /*

             * Run mixed insertion sort on small non-leftmost parts.

             */

            if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {

                mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);

                return;

            /*

             * Invoke insertion sort on small leftmost part.

             */

            if (size < MAX_INSERTION_SORT_SIZE) {

                insertionSort(a, low, high);

                return;

            }

            /*

             * Check if the whole array or large non-leftmost

             * parts are nearly sorted and then merge runs.

             */

            if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)

                    && tryMergeRuns(sorter, a, low, size)) {

                return;

            }

            /*

             * Switch to heap sort if execution

             * time is becoming quadratic.

             */

            if ((bits += DELTA) > MAX_RECURSION_DEPTH) {

                heapSort(a, low, high);

                return;

             * Use an inexpensive approximation of the golden ratio

             * to select five sample elements and determine pivots.

             */

            int step = (size >> 3) * 3 + 3;

            /*

             * Five elements around (and including) the central element

             * 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;

            int a3 = a[e3];

            /*

             * Sort these elements in place by the combination

             * of 4-element sorting network and insertion sort.

             *

             *    5 ------o-----------o------------

             *            |           |

             *    4 ------|-----o-----o-----o------

             *            |     |           |

             *    2 ------o-----|-----o-----o------

             *                  |     |

             *    1 ------------o-----o------------

             */

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

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

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

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

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

            if (a3 < a[e2]) {

                if (a3 < a[e1]) {

                    a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;

                } else {

                    a[e3] = a[e2]; a[e2] = a3;

                }

            } else if (a3 > a[e4]) {

                if (a3 > a[e5]) {

                    a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;

                } else {

                    a[e3] = a[e4]; a[e4] = a3;

                }

            // 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

            /*

             * Partitioning with 2 pivots in case of different elements.

             */

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

                /*

                 * Use the first and fifth of the five sorted 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 the next

                 * 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);

                /*

                 * Backward 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 unused = --lower, k = ++upper; --k > lower; ) {

                    int ak = a[k];

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

                        while (lower < k) {

                            if (a[++lower] >= pivot1) {

                                if (a[lower] > pivot2) {

                                    a[k] = a[--upper];

                                    a[upper] = a[lower];

                                } else {

                                    a[k] = a[lower];

                                }

                                a[lower] = ak;

                                break;

                            }

                        }

                    } 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 non-left parts recursively (possibly in parallel),

                 * excluding known pivots.

                 */

                if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {

                    sorter.forkSorter(bits | 1, lower + 1, upper);

                    sorter.forkSorter(bits | 1, upper + 1, high);

                } else {

                    sort(sorter, a, bits | 1, lower + 1, upper);

                    sort(sorter, a, bits | 1, upper + 1, high);

                }

            } else { // Use single pivot in case of many equal elements

                /*

                 * Use the third of the five sorted elements 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. After

                 * completion of partitioning the pivot is swapped

                 * back into its final position, and excluded from

                 * the next 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; ) {

                    int ak = a[k];

                    if (ak != pivot) {

                        a[k] = pivot;

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

                            while (a[++lower] < pivot);

                            if (a[lower] > pivot) {

                                a[--upper] = a[lower];

                            }

                            a[lower] = ak;

                        } else { // ak > pivot - Move a[k] to the right side

                            a[--upper] = ak;

                        }

                    }

                }

                /*

                 * Swap the pivot into its final position.

                 */

                a[low] = a[lower]; a[lower] = pivot;

                /*

                 * Sort the right part (possibly in parallel), excluding

                 * known pivot. All elements from the central part are

                 * equal and therefore already sorted.

                 */

                if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {

                    sorter.forkSorter(bits | 1, upper, high);

                } else {

                    sort(sorter, a, bits | 1, upper, high);

                }

            high = lower; // Iterate along the left part

     * Sorts the specified range of the array using mixed insertion sort.

     *

     * Mixed insertion sort is combination of simple insertion sort,

     * pin insertion sort and pair insertion sort.

     *

     * In the context of Dual-Pivot Quicksort, the pivot element

     * from the left part plays the role of sentinel, because it

     * is less than any elements from the given part. Therefore,

     * expensive check of the left range can be skipped on each

     * iteration unless it is the leftmost call.

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

     * @param end the index of the last element for simple insertion sort

     * @param high the index of the last element, exclusive, to be sorted

    private static void mixedInsertionSort(int[] a, int low, int end, int high) {

        if (end == high) {

             * Invoke simple insertion sort on tiny array.

            for (int i; ++low < end; ) {

                int ai = a[i = low];

                while (ai < a[--i]) {

                    a[i + 1] = a[i];

                }

                a[i + 1] = ai;

            }

        } else {

             * Start with pin insertion sort on small part.

             * Pin insertion sort is extended simple insertion sort.

             * The main idea of this sort is to put elements larger

             * than an element called pin to the end of array (the

             * proper area for such elements). It avoids expensive

             * movements of these elements through the whole array.

            int pin = a[end];

            for (int i, p = high; ++low < end; ) {

                int ai = a[i = low];

                if (ai < a[i - 1]) { // Small element

                    /*

                     * Insert small element into sorted part.

                     */

                    a[i] = a[--i];

                    while (ai < a[--i]) {

                        a[i + 1] = a[i];

                    a[i + 1] = ai;

                } else if (p > i && ai > pin) { // Large element