/*

 * Copyright (c) 1997, 2011, 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.lang.reflect.*;

/**

 * This class contains various methods for manipulating arrays (such as

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

 * that allows arrays to be viewed as lists.

 *

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

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

 *

 * <p>The documentation for the methods contained in this class includes

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

 * be regarded as <i>implementation notes</i>, rather than parts of the

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

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @author Josh Bloch

 * @author Neal Gafter

 * @author John Rose

 * @since  1.2

 */

public class Arrays {

    // Suppresses default constructor, ensuring non-instantiability.

    private Arrays() {}

    /*

     * Sorting of primitive type 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.

     *

     * @param a the array to be sorted

     */

    public static void sort(int[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

     * 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 a the array to be sorted

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

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

     *

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

     * @throws ArrayIndexOutOfBoundsException

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

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        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.

     *

     * @param a the array to be sorted

     */

    public static void sort(long[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

     * 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 a the array to be sorted

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

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

     *

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

     * @throws ArrayIndexOutOfBoundsException

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

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        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.

     *

     * @param a the array to be sorted

     */

    public static void sort(short[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

     * 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 a the array to be sorted

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

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

     *

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

     * @throws ArrayIndexOutOfBoundsException

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

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        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.

     *

     * @param a the array to be sorted

     */

    public static void sort(char[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

     * 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 a the array to be sorted

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

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

     *

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

     * @throws ArrayIndexOutOfBoundsException

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

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        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.

     *

     * @param a the array to be sorted

     */

    public static void sort(byte[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

     * 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 a the array to be sorted

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

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

     *

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

     * @throws ArrayIndexOutOfBoundsException

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

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        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 all float

     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value

     * {@code 0.0f} and {@code Float.NaN} is considered greater than any

     * other value and all {@code Float.NaN} values are considered 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) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

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

     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value

     * {@code 0.0f} and {@code Float.NaN} is considered greater than any

     * other value and all {@code Float.NaN} values are considered 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, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, 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);

        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 all double

     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value

     * {@code 0.0d} and {@code Double.NaN} is considered greater than any

     * other value and all {@code Double.NaN} values are considered 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(double[] a) {

        DualPivotQuicksort.sort(a);

    }

    /**

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

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

     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value

     * {@code 0.0d} and {@code Double.NaN} is considered greater than any

     * other value and all {@code Double.NaN} values are considered 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, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, 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);

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

    }

    /*

     * Sorting of complex type arrays.

     */

    /**

     * Old merge sort implementation can be selected (for

     * compatibility with broken comparators) using a system property.

     * Cannot be a static boolean in the enclosing class due to

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

     */

    static final class LegacyMergeSort {

        private static final boolean userRequested =

            java.security.AccessController.doPrivileged(

                new sun.security.action.GetBooleanAction(

                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();

    }

    /*

     * If this platform has an optimizing VM, check whether ComparableTimSort

     * offers any performance benefit over TimSort in conjunction with a

     * comparator that returns:

     *    {@code ((Comparable)first).compareTo(Second)}.

     * If not, you are better off deleting ComparableTimSort to

     * eliminate the code duplication.  In other words, the commented

     * out code below is the preferable implementation for sorting

     * arrays of Comparables if it offers sufficient performance.

     */

//    /**

//     * A comparator that implements the natural ordering of a group of

//     * mutually comparable elements.  Using this comparator saves us

//     * from duplicating most of the code in this file (one version for

//     * Comparables, one for explicit Comparators).

//     */

//    private static final Comparator<Object> NATURAL_ORDER =

//            new Comparator<Object>() {

//        @SuppressWarnings("unchecked")

//        public int compare(Object first, Object second) {

//            return ((Comparable<Object>)first).compareTo(second);

//        }

//    };

//

//    public static void sort(Object[] a) {

//        sort(a, 0, a.length, NATURAL_ORDER);

//    }

//

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

//        sort(a, fromIndex, toIndex, NATURAL_ORDER);

//    }

    /**

     * Sorts the specified array of objects into ascending order, according

     * to the {@linkplain Comparable natural ordering} of its elements.

     * All elements in the array must implement the {@link Comparable}

     * interface.  Furthermore, all elements in the array must be

     * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must

     * not throw a {@code ClassCastException} for any elements {@code e1}

     * and {@code e2} in the array).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.

     *

     * <p>Implementation note: This implementation is a stable, adaptive,

     * iterative mergesort that requires far fewer than n lg(n) comparisons

     * when the input array is partially sorted, while offering the

     * performance of a traditional mergesort when the input array is

     * randomly ordered.  If the input array is nearly sorted, the

     * implementation requires approximately n comparisons.  Temporary

     * storage requirements vary from a small constant for nearly sorted

     * input arrays to n/2 object references for randomly ordered input

     * arrays.

     *

     * <p>The implementation takes equal advantage of ascending and

     * descending order in its input array, and can take advantage of

     * ascending and descending order in different parts of the the same

     * input array.  It is well-suited to merging two or more sorted arrays:

     * simply concatenate the arrays and sort the resulting array.

     *

     * <p>The implementation was adapted from Tim Peters's list sort for Python

     * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic

     * Sorting and Information Theoretic Complexity", in Proceedings of the

     * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

     * January 1993.

     *

     * @param a the array to be sorted

     * @throws ClassCastException if the array contains elements that are not

     *         <i>mutually comparable</i> (for example, strings and integers)

     * @throws IllegalArgumentException (optional) if the natural

     *         ordering of the array elements is found to violate the

     *         {@link Comparable} contract

     */

    public static void sort(Object[] a) {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a);

        else

            ComparableTimSort.sort(a);

    }

    /** To be removed in a future release. */

    private static void legacyMergeSort(Object[] a) {

        Object[] aux = a.clone();

        mergeSort(aux, a, 0, a.length, 0);

    }

    /**

     * Sorts the specified range of the specified array of objects into

     * ascending order, according to the

     * {@linkplain Comparable natural ordering} of its

     * elements.  The range to be sorted extends from index

     * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.

     * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All

     * elements in this range must implement the {@link Comparable}

     * interface.  Furthermore, all elements in this range must be <i>mutually

     * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a

     * {@code ClassCastException} for any elements {@code e1} and

     * {@code e2} in the array).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.

     *

     * <p>Implementation note: This implementation is a stable, adaptive,

     * iterative mergesort that requires far fewer than n lg(n) comparisons

     * when the input array is partially sorted, while offering the

     * performance of a traditional mergesort when the input array is

     * randomly ordered.  If the input array is nearly sorted, the

     * implementation requires approximately n comparisons.  Temporary

     * storage requirements vary from a small constant for nearly sorted

     * input arrays to n/2 object references for randomly ordered input

     * arrays.

     *

     * <p>The implementation takes equal advantage of ascending and

     * descending order in its input array, and can take advantage of

     * ascending and descending order in different parts of the the same

     * input array.  It is well-suited to merging two or more sorted arrays:

     * simply concatenate the arrays and sort the resulting array.

     *

     * <p>The implementation was adapted from Tim Peters's list sort for Python

     * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic

     * Sorting and Information Theoretic Complexity", in Proceedings of the

     * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

     * January 1993.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element (inclusive) to be

     *        sorted

     * @param toIndex the index of the last element (exclusive) to be sorted

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

     *         (optional) if the natural ordering of the array elements is

     *         found to violate the {@link Comparable} contract

     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or

     *         {@code toIndex > a.length}

     * @throws ClassCastException if the array contains elements that are

     *         not <i>mutually comparable</i> (for example, strings and

     *         integers).

     */

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

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a, fromIndex, toIndex);

        else

            ComparableTimSort.sort(a, fromIndex, toIndex);

    }

    /** To be removed in a future release. */

    private static void legacyMergeSort(Object[] a,

                                        int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        Object[] aux = copyOfRange(a, fromIndex, toIndex);

        mergeSort(aux, a, fromIndex, toIndex, -fromIndex);

    }

    /**

     * Tuning parameter: list size at or below which insertion sort will be

     * used in preference to mergesort.

     * To be removed in a future release.

     */

    private static final int INSERTIONSORT_THRESHOLD = 7;

    /**

     * Src is the source array that starts at index 0

     * Dest is the (possibly larger) array destination with a possible offset

     * low is the index in dest to start sorting

     * high is the end index in dest to end sorting

     * off is the offset to generate corresponding low, high in src

     * To be removed in a future release.

     */

    private static void mergeSort(Object[] src,

                                  Object[] dest,

                                  int low,

                                  int high,

                                  int off) {

        int length = high - low;

        // Insertion sort on smallest arrays

        if (length < INSERTIONSORT_THRESHOLD) {

            for (int i=low; i<high; i++)

                for (int j=i; j>low &&

                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)

                    swap(dest, j, j-1);

            return;

        }

        // Recursively sort halves of dest into src

        int destLow  = low;

        int destHigh = high;

        low  += off;

        high += off;

        int mid = (low + high) >>> 1;

        mergeSort(dest, src, low, mid, -off);

        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an

        // optimization that results in faster sorts for nearly ordered lists.

        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {

            System.arraycopy(src, low, dest, destLow, length);

            return;

        }

        // Merge sorted halves (now in src) into dest

        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {

            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)

                dest[i] = src[p++];

            else

                dest[i] = src[q++];

        }

    }

    /**

     * Swaps x[a] with x[b].

     */

    private static void swap(Object[] x, int a, int b) {

        Object t = x[a];

        x[a] = x[b];

        x[b] = t;

    }

    /**

     * Sorts the specified array of objects according to the order induced by

     * the specified comparator.  All elements in the array must be

     * <i>mutually comparable</i> by the specified comparator (that is,

     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}

     * for any elements {@code e1} and {@code e2} in the array).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.

     *

     * <p>Implementation note: This implementation is a stable, adaptive,

     * iterative mergesort that requires far fewer than n lg(n) comparisons

     * when the input array is partially sorted, while offering the

     * performance of a traditional mergesort when the input array is

     * randomly ordered.  If the input array is nearly sorted, the

     * implementation requires approximately n comparisons.  Temporary

     * storage requirements vary from a small constant for nearly sorted

     * input arrays to n/2 object references for randomly ordered input

     * arrays.

     *

     * <p>The implementation takes equal advantage of ascending and

     * descending order in its input array, and can take advantage of

     * ascending and descending order in different parts of the the same

     * input array.  It is well-suited to merging two or more sorted arrays:

     * simply concatenate the arrays and sort the resulting array.

     *

     * <p>The implementation was adapted from Tim Peters's list sort for Python

     * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic

     * Sorting and Information Theoretic Complexity", in Proceedings of the

     * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

     * January 1993.

     *

     * @param a the array to be sorted

     * @param c the comparator to determine the order of the array.  A

     *        {@code null} value indicates that the elements'

     *        {@linkplain Comparable natural ordering} should be used.

     * @throws ClassCastException if the array contains elements that are

     *         not <i>mutually comparable</i> using the specified comparator

     * @throws IllegalArgumentException (optional) if the comparator is

     *         found to violate the {@link Comparator} contract

     */

    public static <T> void sort(T[] a, Comparator<? super T> c) {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a, c);

        else

            TimSort.sort(a, c);

    }

    /** To be removed in a future release. */

    private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {

        T[] aux = a.clone();

        if (c==null)

            mergeSort(aux, a, 0, a.length, 0);

        else

            mergeSort(aux, a, 0, a.length, 0, c);

    }

    /**

     * Sorts the specified range of the specified array of objects according

     * to the order induced by the specified comparator.  The range to be

     * sorted extends from index {@code fromIndex}, inclusive, to index

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

     * range to be sorted is empty.)  All elements in the range must be

     * <i>mutually comparable</i> by the specified comparator (that is,

     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}

     * for any elements {@code e1} and {@code e2} in the range).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.

     *

     * <p>Implementation note: This implementation is a stable, adaptive,

     * iterative mergesort that requires far fewer than n lg(n) comparisons

     * when the input array is partially sorted, while offering the

     * performance of a traditional mergesort when the input array is

     * randomly ordered.  If the input array is nearly sorted, the

     * implementation requires approximately n comparisons.  Temporary

     * storage requirements vary from a small constant for nearly sorted

     * input arrays to n/2 object references for randomly ordered input

     * arrays.

     *

     * <p>The implementation takes equal advantage of ascending and

     * descending order in its input array, and can take advantage of

     * ascending and descending order in different parts of the the same

     * input array.  It is well-suited to merging two or more sorted arrays:

     * simply concatenate the arrays and sort the resulting array.

     *

     * <p>The implementation was adapted from Tim Peters's list sort for Python

     * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic

     * Sorting and Information Theoretic Complexity", in Proceedings of the

     * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

     * January 1993.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element (inclusive) to be

     *        sorted

     * @param toIndex the index of the last element (exclusive) to be sorted

     * @param c the comparator to determine the order of the array.  A

     *        {@code null} value indicates that the elements'

     *        {@linkplain Comparable natural ordering} should be used.

     * @throws ClassCastException if the array contains elements that are not

     *         <i>mutually comparable</i> using the specified comparator.

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

     *         (optional) if the comparator is found to violate the

     *         {@link Comparator} contract

     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or

     *         {@code toIndex > a.length}

     */

    public static <T> void sort(T[] a, int fromIndex, int toIndex,

                                Comparator<? super T> c) {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a, fromIndex, toIndex, c);

        else

            TimSort.sort(a, fromIndex, toIndex, c);

    }

    /** To be removed in a future release. */

    private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,

                                            Comparator<? super T> c) {

        rangeCheck(a.length, fromIndex, toIndex);

        T[] aux = copyOfRange(a, fromIndex, toIndex);

        if (c==null)

            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);

        else

            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);

    }

    /**

     * Src is the source array that starts at index 0

     * Dest is the (possibly larger) array destination with a possible offset

     * low is the index in dest to start sorting

     * high is the end index in dest to end sorting

     * off is the offset into src corresponding to low in dest

     * To be removed in a future release.

     */

    private static void mergeSort(Object[] src,

                                  Object[] dest,

                                  int low, int high, int off,

                                  Comparator c) {

        int length = high - low;

        // Insertion sort on smallest arrays

        if (length < INSERTIONSORT_THRESHOLD) {

            for (int i=low; i<high; i++)

                for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)

                    swap(dest, j, j-1);

            return;

        }

        // Recursively sort halves of dest into src

        int destLow  = low;

        int destHigh = high;

        low  += off;

        high += off;

        int mid = (low + high) >>> 1;

        mergeSort(dest, src, low, mid, -off, c);

        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest.  This is an

        // optimization that results in faster sorts for nearly ordered lists.

        if (c.compare(src[mid-1], src[mid]) <= 0) {

           System.arraycopy(src, low, dest, destLow, length);

           return;

        }

        // Merge sorted halves (now in src) into dest

        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {

            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)

                dest[i] = src[p++];

            else

                dest[i] = src[q++];

        }

    }

    /**

     * Checks that {@code fromIndex} and {@code toIndex} are in

     * the range and throws an appropriate exception, if they aren't.

     */

    private static void rangeCheck(int length, int fromIndex, int toIndex) {

        if (fromIndex > toIndex) {

            throw new IllegalArgumentException(

                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");

        }

        if (fromIndex < 0) {

            throw new ArrayIndexOutOfBoundsException(fromIndex);

        }

        if (toIndex > length) {

            throw new ArrayIndexOutOfBoundsException(toIndex);

        }

    }

    // Searching

    /**

     * Searches the specified array of longs for the specified value using the

     * binary search algorithm.  The array must be sorted (as

     * by the {@link #sort(long[])} method) prior to making this call.  If it

     * is not sorted, the results are undefined.  If the array contains

     * multiple elements with the specified value, there is no guarantee which

     * one will be found.

     *

     * @param a the array to be searched

     * @param key the value to be searched for

     * @return index of the search key, if it is contained in the array;

     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     *         <i>insertion point</i> is defined as the point at which the

     *         key would be inserted into the array: the index of the first

     *         element greater than the key, or <tt>a.length</tt> if all

     *         elements in the array are less than the specified key.  Note

     *         that this guarantees that the return value will be >= 0 if

     *         and only if the key is found.

     */

    public static int binarySearch(long[] a, long key) {

        return binarySearch0(a, 0, a.length, key);

    }

    /**

     * Searches a range of

     * the specified array of longs for the specified value using the

     * binary search algorithm.

     * The range must be sorted (as

     * by the {@link #sort(long[], int, int)} method)

     * prior to making this call.  If it

     * is not sorted, the results are undefined.  If the range contains

     * multiple elements with the specified value, there is no guarantee which

     * one will be found.

     *

     * @param a the array to be searched

     * @param fromIndex the index of the first element (inclusive) to be

     *          searched

     * @param toIndex the index of the last element (exclusive) to be searched

     * @param key the value to be searched for

     * @return index of the search key, if it is contained in the array

     *         within the specified range;

     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     *         <i>insertion point</i> is defined as the point at which the

     *         key would be inserted into the array: the index of the first

     *         element in the range greater than the key,

     *         or <tt>toIndex</tt> if all

     *         elements in the range are less than the specified key.  Note

     *         that this guarantees that the return value will be >= 0 if

     *         and only if the key is found.

     * @throws IllegalArgumentException

     *         if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

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

     * @since 1.6

     */

    public static int binarySearch(long[] a, int fromIndex, int toIndex,

                                   long key) {

        rangeCheck(a.length, fromIndex, toIndex);

        return binarySearch0(a, fromIndex, toIndex, key);

    }

    // Like public version, but without range checks.

    private static int binarySearch0(long[] a, int fromIndex, int toIndex,

                                     long key) {

        int low = fromIndex;

        int high = toIndex - 1;

        while (low <= high) {

            int mid = (low + high) >>> 1;

            long midVal = a[mid];

            if (midVal < key)

                low = mid + 1;

            else if (midVal > key)

                high = mid - 1;

            else

                return mid; // key found

        }

        return -(low + 1);  // key not found.

    }

    /**

     * Searches the specified array of ints for the specified value using the

     * binary search algorithm.  The array must be sorted (as

     * by the {@link #sort(int[])} method) prior to making this call.  If it

     * is not sorted, the results are undefined.  If the array contains

     * multiple elements with the specified value, there is no guarantee which

     * one will be found.

     *

     * @param a the array to be searched

     * @param key the value to be searched for

     * @return index of the search key, if it is contained in the array;

     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     *         <i>insertion point</i> is defined as the point at which the

     *         key would be inserted into the array: the index of the first

     *         element greater than the key, or <tt>a.length</tt> if all

     *         elements in the array are less than the specified key.  Note

     *         that this guarantees that the return value will be >= 0 if

     *         and only if the key is found.

     */

    public static int binarySearch(int[] a, int key) {

        return binarySearch0(a, 0, a.length, key);

    }

    /**

     * Searches a range of

     * the specified array of ints for the specified value using the

     * binary search algorithm.

     * The range must be sorted (as

     * by the {@link #sort(int[], int, int)} method)

     * prior to making this call.  If it

     * is not sorted, the results are undefined.  If the range contains

     * multiple elements with the specified value, there is no guarantee which

     * one will be found.

     *

     * @param a the array to be searched

     * @param fromIndex the index of the first element (inclusive) to be

     *          searched

     * @param toIndex the index of the last element (exclusive) to be searched

     * @param key the value to be searched for

     * @return index of the search key, if it is contained in the array

     *         within the specified range;

     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     *         <i>insertion point</i> is defined as the point at which the

     *         key would be inserted into the array: the index of the first

     *         element in the range greater than the key,

     *         or <tt>toIndex</tt> if all

     *         elements in the range are less than the specified key.  Note

     *         that this guarantees that the return value will be >= 0 if

     *         and only if the key is found.

     * @throws IllegalArgumentException

     *         if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

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

     * @since 1.6

     */

    public static int binarySearch(int[] a, int fromIndex, int toIndex,

                                   int key) {

        rangeCheck(a.length, fromIndex, toIndex);

        return binarySearch0(a, fromIndex, toIndex, key);

    }

    // Like public version, but without range checks.

    private static int binarySearch0(int[] a, int fromIndex, int toIndex,

                                     int key) {

        int low = fromIndex;

        int high = toIndex - 1;

        while (low <= high) {

            int mid = (low + high) >>> 1;

            int midVal = a[mid];

            if (midVal < key)

                low = mid + 1;

            else if (midVal > key)

                high = mid - 1;

            else

                return mid; // key found

        }

        return -(low + 1);  // key not found.

    }

    /**

     * Searches the specified array of shorts for the specified value using

     * the binary search algorithm.  The array must be sorted

     * (as by the {@link #sort(short[])} method) prior to making this call.  If

     * it is not sorted, the results are undefined.  If the array contains

     * multiple elements with the specified value, there is no guarantee which

     * one will be found.

     *

     * @param a the array to be searched

     * @param key the value to be searched for

     * @return index of the search key, if it is contained in the array;

     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     *         <i>insertion point</i> is defined as the point at which the

     *         key would be inserted into the array: the index of the first

     *         element greater than the key, or <tt>a.length</tt> if all

     *         elements in the array are less than the specified key.  Note

     *         that this guarantees that the return value will be >= 0 if

     *         and only if the key is found.

     */

    public static int binarySearch(short[] a, short key) {

        return binarySearch0(a, 0, a.length, key);

    }

    /**

     * Searches a range of