Arrays.java

/*
 * Copyright (c) 1997, 2024, 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.
 */

packagejava.util;

importjdk.internal.util.ArraysSupport;
importjdk.internal.vm.annotation.IntrinsicCandidate;

importjava.io.Serializable;
importjava.lang.reflect.Array;
importjava.util.concurrent.ForkJoinPool;
importjava.util.function.BinaryOperator;
importjava.util.function.Consumer;
importjava.util.function.DoubleBinaryOperator;
importjava.util.function.IntBinaryOperator;
importjava.util.function.IntFunction;
importjava.util.function.IntToDoubleFunction;
importjava.util.function.IntToLongFunction;
importjava.util.function.IntUnaryOperator;
importjava.util.function.LongBinaryOperator;
importjava.util.function.UnaryOperator;
importjava.util.stream.DoubleStream;
importjava.util.stream.IntStream;
importjava.util.stream.LongStream;
importjava.util.stream.Stream;
importjava.util.stream.StreamSupport;

/**
 * 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
 * brief descriptions 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}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @author Josh Bloch
 * @author Neal Gafter
 * @author John Rose
 * @since 1.2
 */
publicfinalclassArrays {

// Suppresses default constructor, ensuring non-instantiability.
privateArrays() {}

/*
 * Sorting methods. Note that all public "sort" methods take the
 * same form: performing argument checks if necessary, and then
 * expanding arguments into those required for the internal
 * implementation methods residing in other package-private
 * classes (except for legacyMergeSort, included in this class).
 */

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(int[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(int[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(long[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(long[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(short[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(short[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(char[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(char[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(byte[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(byte[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(float[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(float[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
publicstaticvoidsort(double[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
 }

/**
 * 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.
 *
 * @implNote 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 all data sets, 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}
 */
publicstaticvoidsort(double[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(byte[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(byte[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(char[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(char[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(short[] a) {
DualPivotQuicksort.sort(a, 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(short[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(int[] a) {
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(int[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(long[] a) {
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(long[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

/**
 * 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(float[] a) {
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(float[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

/**
 * 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(double[] a) {
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
 }

/**
 * Sorts the specified range of the array into ascending numerical 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.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @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}
 *
 * @since 1.8
 */
publicstaticvoidparallelSort(double[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

/**
 * Checks that {@code fromIndex} and {@code toIndex} are in
 * the range and throws an exception if they aren't.
 */
staticvoidrangeCheck(intarrayLength, intfromIndex, inttoIndex) {
if (fromIndex > toIndex) {
thrownewIllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
 }
if (fromIndex < 0) {
thrownewArrayIndexOutOfBoundsException(fromIndex);
 }
if (toIndex > arrayLength) {
thrownewArrayIndexOutOfBoundsException(toIndex);
 }
 }

/**
 * A comparator that implements the natural ordering of a group of
 * mutually comparable elements. May be used when a supplied
 * comparator is null. To simplify code-sharing within underlying
 * implementations, the compare method only declares type Object
 * for its second argument.
 *
 * Arrays class implementor's note: It is an empirical matter
 * whether ComparableTimSort offers any performance benefit over
 * TimSort used with this comparator. If not, you are better off
 * deleting or bypassing ComparableTimSort. There is currently no
 * empirical case for separating them for parallel sorting, so all
 * public Object parallelSort methods use the same comparator
 * based implementation.
 */
staticfinalclassNaturalOrderimplementsComparator<Object> {
@SuppressWarnings("unchecked")
publicintcompare(Objectfirst, Objectsecond) {
return ((Comparable<Object>)first).compareTo(second);
 }
staticfinalNaturalOrderINSTANCE = newNaturalOrder();
 }

/**
 * The minimum array length below which a parallel sorting
 * algorithm will not further partition the sorting task. Using
 * smaller sizes typically results in memory contention across
 * tasks that makes parallel speedups unlikely.
 */
privatestaticfinalintMIN_ARRAY_SORT_GRAN = 1 << 13;

/**
 * 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.
 *
 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
 * array into sub-arrays that are themselves sorted and then merged. When
 * the sub-array length reaches a minimum granularity, the sub-array is
 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
 * method. If the length of the specified array is less than the minimum
 * granularity, then it is sorted using the appropriate {@link
 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
 * working space no greater than the size of the original array. The
 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
 * execute any parallel tasks.
 *
 * @param <T> the class of the objects to be sorted
 * @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
 *
 * @since 1.8
 */
@SuppressWarnings("unchecked")
publicstatic <TextendsComparable<? superT>> voidparallelSort(T[] a) {
intn = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
newArraysParallelSortHelpers.FJObject.Sorter<>
 (null, a,
 (T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
 }

/**
 * 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.
 *
 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
 * array into sub-arrays that are themselves sorted and then merged. When
 * the sub-array length reaches a minimum granularity, the sub-array is
 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
 * method. If the length of the specified array is less than the minimum
 * granularity, then it is sorted using the appropriate {@link
 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working
 * space no greater than the size of the specified range of the original
 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
 * used to execute any parallel tasks.
 *
 * @param <T> the class of the objects to be sorted
 * @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).
 *
 * @since 1.8
 */
@SuppressWarnings("unchecked")
publicstatic <TextendsComparable<? superT>>
voidparallelSort(T[] a, intfromIndex, inttoIndex) {
rangeCheck(a.length, fromIndex, toIndex);
intn = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
else
newArraysParallelSortHelpers.FJObject.Sorter<>
 (null, a,
 (T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
 }

/**
 * 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.
 *
 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
 * array into sub-arrays that are themselves sorted and then merged. When
 * the sub-array length reaches a minimum granularity, the sub-array is
 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
 * method. If the length of the specified array is less than the minimum
 * granularity, then it is sorted using the appropriate {@link
 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
 * working space no greater than the size of the original array. The
 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
 * execute any parallel tasks.
 *
 * @param <T> the class of the objects to be sorted
 * @param a the array to be sorted
 * @param cmp 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 java.util.Comparator} contract
 *
 * @since 1.8
 */
@SuppressWarnings("unchecked")
publicstatic <T> voidparallelSort(T[] a, Comparator<? superT> cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
intn = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0);
else
newArraysParallelSortHelpers.FJObject.Sorter<>
 (null, a,
 (T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
 }

/**
 * 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.
 *
 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
 * array into sub-arrays that are themselves sorted and then merged. When
 * the sub-array length reaches a minimum granularity, the sub-array is
 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
 * method. If the length of the specified array is less than the minimum
 * granularity, then it is sorted using the appropriate {@link
 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working
 * space no greater than the size of the specified range of the original
 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
 * used to execute any parallel tasks.
 *
 * @param <T> the class of the objects to be sorted
 * @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 cmp 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 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).
 *
 * @since 1.8
 */
@SuppressWarnings("unchecked")
publicstatic <T> voidparallelSort(T[] a, intfromIndex, inttoIndex,
Comparator<? superT> cmp) {
rangeCheck(a.length, fromIndex, toIndex);
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
intn = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
else
newArraysParallelSortHelpers.FJObject.Sorter<>
 (null, a,
 (T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
 }

/*
 * 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.
 */
staticfinalclassLegacyMergeSort {
privatestaticfinalbooleanuserRequested =
Boolean.getBoolean("java.util.Arrays.useLegacyMergeSort");
 }

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