* Copyright 1997-2009 Sun Microsystems, Inc.  All Rights Reserved.

 * sorting and searching). This class also contains a static factory

 * <p>The methods in this class all throw a {@code NullPointerException},

 * if the specified array reference is null, except where noted.

 * briefs description of the <i>implementations</i>. Such descriptions should

 * <i>specification</i>. Implementors should feel free to substitute other

 * algorithms, so long as the specification itself is adhered to. (For

 * example, the algorithm used by {@code sort(Object[])} does not have to be

 * a MergeSort, but it does have to be <i>stable</i>.)

 * @author Josh Bloch

 * @author Neal Gafter

 * @author John Rose

 * @since  1.2

public class Arrays {

    private Arrays() {}

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

     * Sorts the specified array into ascending numerical order.

     *

     * <p>The {@code <} relation does not provide a total order on

     * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares

     * neither less than, greater than, nor equal to any floating-point

     * value, even itself. To allow the sort to proceed, instead of using

     * the {@code <} relation to determine ascending numerical order,

     * this method uses the total order imposed by {@link Double#compareTo}.

     * This ordering differs from the {@code <} relation in that {@code -0.0d}

     * is treated as less than {@code 0.0d} and NaN is considered greater than

     * any other floating-point value. For the purposes of sorting, all NaN

     * values are considered equivalent and equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

        sort(a, 0, a.length);

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>The {@code <} relation does not provide a total order on

     * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares

     * neither less than, greater than, nor equal to any floating-point

     * value, even itself. To allow the sort to proceed, instead of using

     * the {@code <} relation to determine ascending numerical order,

     * this method uses the total order imposed by {@link Double#compareTo}.

     * This ordering differs from the {@code <} relation in that {@code -0.0d}

     * is treated as less than {@code 0.0d} and NaN is considered greater than

     * any other floating-point value. For the purposes of sorting, all NaN

     * values are considered equivalent and equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

    public static void sort(double[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        sortNegZeroAndNaN(a, fromIndex, toIndex);

    private static void sortNegZeroAndNaN(double[] a, int fromIndex, int toIndex) {

         * NaN and -0.0d aware comparisons during the main sort.

         *

         * Preprocessing phase: move any NaN's to end of array, count the

         * number of -0.0d's, and turn them into 0.0d's.

        int i = fromIndex;

        int n = toIndex;

        double temp;

        while (i < n) {

                n--;

                temp = a[i];

                a[i] = a[n];

                a[n] = temp;

            }

            else {

                if (a[i] == 0 && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) {

        DualPivotQuicksort.sort(a, fromIndex, n - 1);

        // Postprocessing phase: change 0.0d's to -0.0d's as required

            int j = binarySearch0(a, fromIndex, n, 0.0d); // position of ANY zero

            }

            while (j >= fromIndex && a[j] == 0.0d);

            for (int k = 0; k < numNegZeros; k++) {

            }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>The {@code <} relation does not provide a total order on

     * all floating-point values; although they are distinct numbers

     * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares

     * neither less than, greater than, nor equal to any floating-point

     * value, even itself. To allow the sort to proceed, instead of using

     * the {@code <} relation to determine ascending numerical order,

     * this method uses the total order imposed by {@link Float#compareTo}.

     * This ordering differs from the {@code <} relation in that {@code -0.0f}

     * is treated as less than {@code 0.0f} and NaN is considered greater than

     * any other floating-point value. For the purposes of sorting, all NaN

     * values are considered equivalent and equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     *

     * @param a the array to be sorted

     */

    public static void sort(float[] a) {

        sort(a, 0, a.length);

    }

    /**

     * Sorts the specified range of the specified array into ascending order. The

     * range of to be sorted extends from the index {@code fromIndex}, inclusive,

     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>The {@code <} relation does not provide a total order on

     * all floating-point values; although they are distinct numbers

     * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares

     * neither less than, greater than, nor equal to any floating-point

     * value, even itself. To allow the sort to proceed, instead of using

     * the {@code <} relation to determine ascending numerical order,

     * this method uses the total order imposed by {@link Float#compareTo}.

     * This ordering differs from the {@code <} relation in that {@code -0.0f}

     * is treated as less than {@code 0.0f} and NaN is considered greater than

     * any other floating-point value. For the purposes of sorting, all NaN

     * values are considered equivalent and equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

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

     * quicksorts to degrade to quadratic performance, and is typically

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

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusively, to be sorted

     * @param toIndex the index of the last element, exclusively, to be sorted

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(float[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        sortNegZeroAndNaN(a, fromIndex, toIndex);

    }

    private static void sortNegZeroAndNaN(float[] a, int fromIndex, int toIndex) {

         * NaN and -0.0f aware comparisons during the main sort.

         *

         * Preprocessing phase: move any NaN's to end of array, count the

         * number of -0.0f's, and turn them into 0.0f's.

        int i = fromIndex;

        int n = toIndex;

        float temp;

        while (i < n) {

                n--;

                temp = a[i];

                a[i] = a[n];

                a[n] = temp;

            }

            else {

                if (a[i] == 0 && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) {

        DualPivotQuicksort.sort(a, fromIndex, n - 1);

        // Postprocessing phase: change 0.0f's to -0.0f's as required

            int j = binarySearch0(a, fromIndex, n, 0.0f); // position of ANY zero

            }

            while (j >= fromIndex && a[j] == 0.0f);

            for (int k = 0; k < numNegZeros; k++) {

     * circular dependencies. To be removed in a future release.