/*
 * Copyright (c) 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.RecursiveTask;

/**
 * This class implements sorting algorithms by Vladimir Yaroslavskiy,
   such as Merging sort, the pair, nano and optimized insertion sorts,
 * counting sort and heap sort, invoked from the Dual-Pivot Quicksort.
 *
 * @author Vladimir Yaroslavskiy
 *
 * @version 2018.02.18
 * @since 10
 */
final class SortingAlgorithms {

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

    /**
     * The minimal number of runs, required by parallel Merging sort.
     */
    private static final int MIN_PARALLEL_RUNS_COUNT = 4;

    /**
     * If the length of an array to be sorted is greater than this
     * constant, Merging sort is used in preference to Quicksort.
     */
    private static final int MERGING_SORT_THRESHOLD = 2048;

    /**
     * Calculates the maximum number of runs.
     *
     * @param length the array length
     * @return the maximum number of runs
     */
    private static int getMaxRunCount(int length) {
        return length > 2048000 ? 2000 : length >> 10 | 5;
    }

    /**
     * This class implements the parallel Merging sort.
     */
    @SuppressWarnings("serial")
    private static class Merger<T> extends RecursiveTask<T> {

        Merger(T a, T b, boolean src, int offset, int[] run, int lo, int hi) {
            this.a = a;
            this.b = b;
            this.src = src;
            this.offset = offset;
            this.run = run;
            this.lo = lo;
            this.hi = hi;
        }

        @Override
        @SuppressWarnings("unchecked")
        protected T compute() {
            Class<?> clazz = a.getClass();

            if (clazz == int[].class) {
                return (T) merge((int[]) a, (int[]) b, src, true, offset, run, lo, hi);
            }
            if (clazz == long[].class) {
                return (T) merge((long[]) a, (long[]) b, src, true, offset, run, lo, hi);
            }
            if (clazz == char[].class) {
                return (T) merge((char[]) a, (char[]) b, src, true, offset, run, lo, hi);
            }
            if (clazz == short[].class) {
                return (T) merge((short[]) a, (short[]) b, src, true, offset, run, lo, hi);
            }
            if (clazz == float[].class) {
                return (T) merge((float[]) a, (float[]) b, src, true, offset, run, lo, hi);
            }
            if (clazz == double[].class) {
                return (T) merge((double[]) a, (double[]) b, src, true, offset, run, lo, hi);
            }
            throw new IllegalArgumentException(
                "Unknown type of array: " + clazz.getName());
        }

        private T a;
        private T b;
        private boolean src;
        private int offset;
        private int[] run;
        private int lo;
        private int hi;
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(int[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    int ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (int ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new int[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static int[] merge(int[] a, int[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        int[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<int[]> merger1 = new Merger<int[]>(a, b, !src, offset, run, lo, mi);
            Merger<int[]> merger2 = new Merger<int[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static int[] merge(int[] dst, int k,
            int[] a1, int i, int hi, int[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(long[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    long ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (long ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new long[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static long[] merge(long[] a, long[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        long[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<long[]> merger1 = new Merger<long[]>(a, b, !src, offset, run, lo, mi);
            Merger<long[]> merger2 = new Merger<long[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static long[] merge(long[] dst, int k,
            long[] a1, int i, int hi, long[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(char[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    char ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (char ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new char[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static char[] merge(char[] a, char[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        char[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<char[]> merger1 = new Merger<char[]>(a, b, !src, offset, run, lo, mi);
            Merger<char[]> merger2 = new Merger<char[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static char[] merge(char[] dst, int k,
            char[] a1, int i, int hi, char[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(short[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    short ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (short ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new short[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static short[] merge(short[] a, short[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        short[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<short[]> merger1 = new Merger<short[]>(a, b, !src, offset, run, lo, mi);
            Merger<short[]> merger2 = new Merger<short[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static short[] merge(short[] dst, int k,
            short[] a1, int i, int hi, short[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(float[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    float ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (float ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new float[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static float[] merge(float[] a, float[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        float[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<float[]> merger1 = new Merger<float[]>(a, b, !src, offset, run, lo, mi);
            Merger<float[]> merger2 = new Merger<float[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static float[] merge(float[] dst, int k,
            float[] a1, int i, int hi, float[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Tries to sort the specified range of the array by the Merging sort.
     *
     * @param a the array to be sorted
     * @param parallel indicates whether merging 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
     * @return true if the given array is finally sorted, false otherwise
     */
    static boolean mergingSort(double[] a, boolean parallel, int low, int high) {
        int length = high - low;

        if (length < MERGING_SORT_THRESHOLD) {
            return false;
        }

        /*
         * Index run[i] is the start of i-th run.
         * A run is a subsequence of elements
         * in ascending or descending order.
         */
        int max = getMaxRunCount(length);
        int[] run = new int[max + 1];
        int count = 0, last = low; run[0] = low;

        /*
         * Check if the array is highly structured.
         */
        for (int k = low + 1; k < high && count < max; ) {
            if (a[k - 1] < a[k]) {

                // Identify ascending sequence
                while (++k < high && a[k - 1] <= a[k]);

            } else if (a[k - 1] > a[k]) {

                // Identify descending sequence
                while (++k < high && a[k - 1] >= a[k]);

                // Reverse the run into ascending order
                for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
                    double ai = a[i]; a[i] = a[j]; a[j] = ai;
                }
            } else { // Sequence with equal elements
                for (double ak = a[k]; ++k < high && ak == a[k]; );

                if (k < high) {
                    continue;
                }
            }

            if (count == 0 || a[last - 1] > a[last]) {
                ++count;
            }
            run[count] = (last = k);
        }

        if (count < max && count > 1) {
            /*
             * The array is highly structured, therefore merge all runs.
             */
            merge(a, new double[length], true, parallel, low, run, 0, count);
        }
        return count < max;
    }

    /**
     * Merges the specified runs.
     *
     * @param a the source array
     * @param b the temporary buffer
     * @param src specifies the type of the target: source or buffer
     * @param parallel indicates whether merging is performed in parallel
     * @param offset the start index of the source, inclusive
     * @param run the start indexes of the runs, inclusive
     * @param lo the start index of the first run, inclusive
     * @param hi the start index of the last run, inclusive
     * @return the target where runs are merged
     */
    private static double[] merge(double[] a, double[] b, boolean src,
            boolean parallel, int offset, int[] run, int lo, int hi) {

        if (hi - lo == 1) {
            if (src) {
                return a;
            }
            for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
                b[--j] = a[--i]
            );
            return b;
        }
        int mi = (lo + hi) >>> 1;

        double[] a1, a2; // the left and the right halves to be merged

        if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
            Merger<double[]> merger1 = new Merger<double[]>(a, b, !src, offset, run, lo, mi);
            Merger<double[]> merger2 = new Merger<double[]>(a, b, true, offset, run, mi, hi);

            ForkJoinTask.invokeAll(merger1, merger2);

            a1 = merger1.getRawResult();
            a2 = merger2.getRawResult();
        } else {
            a1 = merge(a, b, !src, false, offset, run, lo, mi);
            a2 = merge(a, b, true, false, offset, run, mi, hi);
        }
        return merge(
            a1 == a ? b : a,
            a1 == a ? run[lo] - offset : run[lo],
            a1,
            a1 == b ? run[lo] - offset : run[lo],
            a1 == b ? run[mi] - offset : run[mi],
            a2,
            a2 == b ? run[mi] - offset : run[mi],
            a2 == b ? run[hi] - offset : run[hi]);
    }

    /**
     * Merges the sorted halves.
     *
     * @param dst the destination where halves are merged
     * @param k the start index of the destination, inclusive
     * @param a1 the first half
     * @param i the start index of the first half, inclusive
     * @param hi the end index of the first half, exclusive
     * @param a2 the second half
     * @param j the start index of the second half, inclusive
     * @param hj the end index of the second half, exclusive
     * @return the merged halves
     */
    private static double[] merge(double[] dst, int k,
            double[] a1, int i, int hi, double[] a2, int j, int hj) {

        while (true) {
            dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];

            if (i == hi) {
                while (j < hj) {
                    dst[k++] = a2[j++];
                }
                return dst;
            }
            if (j == hj) {
                while (i < hi) {
                    dst[k++] = a1[i++];
                }
                return dst;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(int[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            int ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(long[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            long ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(char[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            char ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(short[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            short ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(float[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            float ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the nano insertion sort.
     *
     * @param a the array to be sorted
     * @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 nanoInsertionSort(double[] a, int low, int high) {
        /*
         * In the context of Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check of the
         * left range on each iteration can be skipped.
         */
        for (int k; ++low < high; ) {
            double ak = a[k = low];

            while (ak < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = ak;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(int[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            int a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                int a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(long[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            long a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                long a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(char[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            char a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                char a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(short[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            short a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                short a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(float[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            float a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                float a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by the pair insertion sort.
     *
     * @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 pairInsertionSort(double[] a, int left, int right) {
        /*
         * Allign the left boundary.
         */
        left -= (left ^ right) & 1;

        /*
         * Two elements are inserted at once on each iteration.
         * At first, we insert the greater element (a2) and then
         * insert the less element (a1), but from position where
         * the greater element was inserted. In the context of a
         * Dual-Pivot Quicksort, the elements from the left part
         * play the role of sentinels. Therefore expensive check
         * of the left range on each iteration can be skipped.
         */
        for (int k; ++left < right; ) {
            double a1 = a[k = ++left];

            if (a[k - 2] > a[k - 1]) {
                double a2 = a[--k];

                if (a1 > a2) {
                    a2 = a1; a1 = a[k];
                }
                while (a2 < a[--k]) {
                    a[k + 2] = a[k];
                }
                a[++k + 1] = a2;
            }
            while (a1 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a1;
        }
    }

    /**
     * Sorts the specified range of the array by optimized insertion sort.
     *
     * @param a the array to be sorted
     * @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 insertionSort(byte[] a, int low, int high) {
        for (int i, k = low; ++k < high; ) {
            byte ak = a[i = k];

            if (ak < a[low]) {
                a[i] = a[low]; a[low] = ak; ak = a[i];
            }
            while (ak < a[--i]) {
                a[i + 1] = a[i];
            }
            a[i + 1] = ak;
        }
    }

    /**
     * The number of distinct byte values.
     */
    private static final int NUM_BYTE_VALUES = 1 << 8;

    /**
     * Sorts the specified range of the array by the counting sort.
     *
     * @param a the array to be sorted
     * @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 countingSort(byte[] a, int low, int high) {
        int[] count = new int[NUM_BYTE_VALUES];

        /*
         * Compute a histogram with the number of each values.
         */
        for (int i = low; i < high; ++i) {
            ++count[a[i] - Byte.MIN_VALUE];
        }

        /*
         * Place values on their final positions.
         */
        for (int i = NUM_BYTE_VALUES, k = high; k > low; ) {
            while (count[--i] == 0);
            byte value = (byte) (i + Byte.MIN_VALUE);
            for (int j = count[i]; --j >= 0; a[--k] = value);
        }
    }

    /**
     * The number of distinct char values.
     */
    private static final int NUM_CHAR_VALUES = 1 << 16;

    /**
     * Sorts the specified range of the array by the counting sort.
     *
     * @param a the array to be sorted
     * @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 countingSort(char[] a, int low, int high) {
        int[] count = new int[NUM_CHAR_VALUES];

        /*
         * Compute a histogram with the number of each values.
         */
        for (int i = low; i < high; ++i) {
            ++count[a[i]];
        }

        /*
         * Place values on their final positions.
         */
        for (int i = NUM_CHAR_VALUES, k = high; k > low; ) {
            while (count[--i] == 0);
            char value = (char) i;
            for (int j = count[i]; --j >= 0; a[--k] = value);
        }
    }

    /**
     * The number of distinct short values.
     */
    private static final int NUM_SHORT_VALUES = 1 << 16;

    /**
     * Sorts the specified range of the array by the counting sort.
     *
     * @param a the array to be sorted
     * @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 countingSort(short[] a, int low, int high) {
        int[] count = new int[NUM_SHORT_VALUES];

        /*
         * Compute a histogram with the number of each values.
         */
        for (int i = low; i < high; ++i) {
            ++count[a[i] - Short.MIN_VALUE];
        }

        /*
         * Place values on their final positions.
         */
        for (int i = NUM_SHORT_VALUES, k = high; k > low; ) {
            while (count[--i] == 0);
            short value = (short) (i + Short.MIN_VALUE);
            for (int j = count[i]; --j >= 0; a[--k] = value);
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(int[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            int max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(int[] a, int p, int value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(long[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            long max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(long[] a, int p, long value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(char[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            char max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(char[] a, int p, char value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(short[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            short max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(short[] a, int p, short value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(float[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            float max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(float[] a, int p, float value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }

    /**
     * Sorts the specified range of the array by the heap sort.
     *
     * @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 heapSort(double[] a, int left, int right) {
        for (int k = (left + 1 + right) >>> 1; k > left; ) {
            pushDown(a, --k, a[k], left, right);
        }
        for (int k = right; k > left; --k) {
            double max = a[left];
            pushDown(a, left, a[k], left, k);
            a[k] = max;
        }
    }

    /**
     * Pushes specified element down during the heap sort.
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void pushDown(double[] a, int p, double value, int left, int right) {
        for (int k ;; a[p] = a[p = k]) {
            k = (p << 1) - left + 2; // the index of the right child

            if (k > right || a[k - 1] > a[k]) {
                --k;
            }
            if (k > right || a[k] <= value) {
                a[p] = value;
                return;
            }
        }
    }
}