Quelle Arrays.java Sprache: JAVA

/*
* Copyright (c) 1997, 2023, 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 jdk.internal.util.ArraysSupport;
import jdk.internal.vm.annotation.IntrinsicCandidate;

import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.concurrent.ForkJoinPool;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.DoubleBinaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.UnaryOperator;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;
import java.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.
*
* The methods in this class all throw a {@code NullPointerException},
* if the specified array reference is null, except where noted.
*
* The documentation for the methods contained in this class includes
* brief descriptions of the implementations. Such descriptions should
* be regarded as implementation notes, rather than parts of the
* specification. 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 stable.)
*
* 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
*/
public class Arrays {

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

 /*
 * 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
 */
 public static void sort(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}
 */
 public static void sort(int[] a, int fromIndex, int toIndex) {
 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
 */
 public static void sort(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}
 */
 public static void sort(long[] a, int fromIndex, int toIndex) {
 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
 */
 public static void sort(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}
 */
 public static void sort(short[] a, int fromIndex, int toIndex) {
 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
 */
 public static void sort(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}
 */
 public static void sort(char[] a, int fromIndex, int toIndex) {
 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
 */
 public static void sort(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}
 */
 public static void sort(byte[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 DualPivotQuicksort.sort(a, fromIndex, toIndex);
 }

 /**
 * Sorts the specified array into ascending numerical order.
 *
 * 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
 */
 public static void sort(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.
 *
 * 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}
 */
 public static void sort(float[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
 }

 /**
 * Sorts the specified array into ascending numerical order.
 *
 * 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
 */
 public static void sort(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.
 *
 * 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}
 */
 public static void sort(double[] a, int fromIndex, int toIndex) {
 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
 */
 public static void parallelSort(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
 */
 public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
 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
 */
 public static void parallelSort(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
 */
 public static void parallelSort(char[] a, int fromIndex, int toIndex) {
 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
 */
 public static void parallelSort(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
 */
 public static void parallelSort(short[] a, int fromIndex, int toIndex) {
 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
 */
 public static void parallelSort(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
 */
 public static void parallelSort(int[] a, int fromIndex, int toIndex) {
 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
 */
 public static void parallelSort(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
 */
 public static void parallelSort(long[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

 /**
 * Sorts the specified array into ascending numerical order.
 *
 * 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
 */
 public static void parallelSort(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.
 *
 * 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
 */
 public static void parallelSort(float[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
 }

 /**
 * Sorts the specified array into ascending numerical order.
 *
 * 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
 */
 public static void parallelSort(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.
 *
 * 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
 */
 public static void parallelSort(double[] a, int fromIndex, int toIndex) {
 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.
 */
 static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
 if (fromIndex > toIndex) {
 throw new IllegalArgumentException(
 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
 }
 if (fromIndex < 0) {
 throw new ArrayIndexOutOfBoundsException(fromIndex);
 }
 if (toIndex > arrayLength) {
 throw new ArrayIndexOutOfBoundsException(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.
 */
 static final class NaturalOrder implements Comparator<Object> {
 @SuppressWarnings("unchecked")
 public int compare(Object first, Object second) {
 return ((Comparable<Object>)first).compareTo(second);
 }
 static final NaturalOrder INSTANCE = new NaturalOrder();
 }

 /**
 * 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.
 */
 private static final int MIN_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
 * mutually comparable (that is, {@code e1.compareTo(e2)} must
 * not throw a {@code ClassCastException} for any elements {@code e1}
 * and {@code e2} in the array).
 *
 * This sort is guaranteed to be stable: 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
 * mutually comparable (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")
 public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
 int n = 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
 new ArraysParallelSortHelpers.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 mutually
 * comparable (that is, {@code e1.compareTo(e2)} must not throw a
 * {@code ClassCastException} for any elements {@code e1} and
 * {@code e2} in the array).
 *
 * This sort is guaranteed to be stable: 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 mutually comparable (for example, strings and
 * integers).
 *
 * @since 1.8
 */
 @SuppressWarnings("unchecked")
 public static <T extends Comparable<? super T>>
 void parallelSort(T[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 int n = 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
 new ArraysParallelSortHelpers.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
 * mutually comparable 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).
 *
 * This sort is guaranteed to be stable: 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 mutually comparable 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")
 public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
 if (cmp == null)
 cmp = NaturalOrder.INSTANCE;
 int n = a.length, p, g;
 if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
 TimSort.sort(a, 0, n, cmp, null, 0, 0);
 else
 new ArraysParallelSortHelpers.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
 * mutually comparable 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).
 *
 * This sort is guaranteed to be stable: 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 mutually comparable (for example, strings and
 * integers).
 *
 * @since 1.8
 */
 @SuppressWarnings("unchecked")
 public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
 Comparator<? super T> cmp) {
 rangeCheck(a.length, fromIndex, toIndex);
 if (cmp == null)
 cmp = NaturalOrder.INSTANCE;
 int n = toIndex - fromIndex, p, g;
 if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
 TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
 else
 new ArraysParallelSortHelpers.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.
 */
 static final class LegacyMergeSort {
 @SuppressWarnings("removal")
 private static final boolean userRequested =
 java.security.AccessController.doPrivileged(
 new sun.security.action.GetBooleanAction(
 "java.util.Arrays.useLegacyMergeSort")).booleanValue();
 }

 /**
 * 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
 * mutually comparable (that is, {@code e1.compareTo(e2)} must
 * not throw a {@code ClassCastException} for any elements {@code e1}
 * and {@code e2} in the array).
 *
 * This sort is guaranteed to be stable: equal elements will
 * not be reordered as a result of the sort.
 *
 * 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.
 *
 * 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 same
 * input array. It is well-suited to merging two or more sorted arrays:
 * simply concatenate the arrays and sort the resulting array.
 *
 * 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 techniques 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
 * mutually comparable (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, 0, a.length, null, 0, 0);
 }

 /** 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 mutually
 * comparable (that is, {@code e1.compareTo(e2)} must not throw a
 * {@code ClassCastException} for any elements {@code e1} and
 * {@code e2} in the array).
 *
 * This sort is guaranteed to be stable: equal elements will
 * not be reordered as a result of the sort.
 *
 * 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.
 *
 * 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 same
 * input array. It is well-suited to merging two or more sorted arrays:
 * simply concatenate the arrays and sort the resulting array.
 *
 * 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 techniques 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 mutually comparable (for example, strings and
 * integers).
 */
 public static void sort(Object[] a, int fromIndex, int toIndex) {
 rangeCheck(a.length, fromIndex, toIndex);
 if (LegacyMergeSort.userRequested)
 legacyMergeSort(a, fromIndex, toIndex);
 else
 ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
 }

 /** To be removed in a future release. */
 private static void legacyMergeSort(Object[] a,
 int fromIndex, int 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.
 */
 @SuppressWarnings({"unchecked", "rawtypes"})
 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
 * mutually comparable 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).
 *
 * This sort is guaranteed to be stable: equal elements will
 * not be reordered as a result of the sort.
 *
 * 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.
 *
 * 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 same
 * input array. It is well-suited to merging two or more sorted arrays:
 * simply concatenate the arrays and sort the resulting array.
 *
 * 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 techniques 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 <T> the class of the objects to be sorted
 * @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 mutually comparable 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 (c == null) {
 sort(a);
 } else {
 if (LegacyMergeSort.userRequested)
 legacyMergeSort(a, c);
 else
 TimSort.sort(a, 0, a.length, c, null, 0, 0);
 }
 }

 /** 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
 * mutually comparable 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).
 *
 * This sort is guaranteed to be stable: equal elements will
 * not be reordered as a result of the sort.
 *
 * 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.
 *
 * 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 same
 * input array. It is well-suited to merging two or more sorted arrays:
 * simply concatenate the arrays and sort the resulting array.
 *
 * 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 techniques 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 <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 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
 * mutually comparable 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 (c == null) {
 sort(a, fromIndex, toIndex);
 } else {
 rangeCheck(a.length, fromIndex, toIndex);
 if (LegacyMergeSort.userRequested)
 legacyMergeSort(a, fromIndex, toIndex, c);
 else
 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
 }
 }

 /** To be removed in a future release. */
 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
 Comparator<? super T> c) {
 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.
 */
 @SuppressWarnings({"rawtypes", "unchecked"})
 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++];
 }
 }

 // Parallel prefix

 /**
 * Cumulates, in parallel, each element of the given array in place,
 * using the supplied function. For example if the array initially
 * holds {@code [2, 1, 0, 3]} and the operation performs addition,
 * then upon return the array holds {@code [2, 3, 3, 6]}.
 * Parallel prefix computation is usually more efficient than
 * sequential loops for large arrays.
 *
 * @param <T> the class of the objects in the array
 * @param array the array, which is modified in-place by this method
 * @param op a side-effect-free, associative function to perform the
 * cumulation
 * @throws NullPointerException if the specified array or function is null
 * @since 1.8
 */
 public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
 Objects.requireNonNull(op);
 if (array.length > 0)
 new ArrayPrefixHelpers.CumulateTask<>
 (null, op, array, 0, array.length).invoke();
 }

 /**
 * Performs {@link #parallelPrefix(Object[], BinaryOperator)}
 * for the given subrange of the array.
 *
 * @param <T> the class of the objects in the array
 * @param array the array
 * @param fromIndex the index of the first element, inclusive
 * @param toIndex the index of the last element, exclusive
 * @param op a side-effect-free, associative function to perform the
 * cumulation
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 * @throws ArrayIndexOutOfBoundsException
 * if {@code fromIndex < 0} or {@code toIndex > array.length}
 * @throws NullPointerException if the specified array or function is null
 * @since 1.8
 */
 public static <T> void parallelPrefix(T[] array, int fromIndex,
--> --------------------

--> maximum size reached

--> --------------------

quality92%

¤ Dauer der Verarbeitung: 0.48 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.