/* * 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.
*/
/** * 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
*/ publicclass 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
*/ publicstaticvoid 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}
*/ publicstaticvoid 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
*/ publicstaticvoid 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}
*/ publicstaticvoid 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
*/ publicstaticvoid 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}
*/ publicstaticvoid 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
*/ publicstaticvoid 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}
*/ publicstaticvoid 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
*/ publicstaticvoid 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}
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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. * * <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}
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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. * * <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}
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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. * * <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
*/ publicstaticvoid 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.
*/ staticvoid rangeCheck(int arrayLength, int fromIndex, int toIndex) { if (fromIndex > toIndex) { thrownew IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
} if (fromIndex < 0) { thrownew ArrayIndexOutOfBoundsException(fromIndex);
} if (toIndex > arrayLength) { thrownew 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.
*/ staticfinalclass NaturalOrder implements Comparator<Object> {
@SuppressWarnings("unchecked") publicint compare(Object first, Object second) { return ((Comparable<Object>)first).compareTo(second);
} staticfinal 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.
*/ privatestaticfinalint 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 * <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 <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 <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 <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 * <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> 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 * <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> 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.
*/ staticfinalclass LegacyMergeSort {
@SuppressWarnings("removal") privatestaticfinalboolean 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 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must * not throw a {@code ClassCastException} for any elements {@code e1} * and {@code e2} in the array). * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will * not be reordered as a result of the sort. * * <p>Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * * <p>The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * * <p>The implementation was adapted from Tim Peters's list sort for Python * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> * TimSort</a>). It uses 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 * <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
*/ publicstaticvoid 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. */ privatestaticvoid legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
/** * Sorts the specified range of the specified array of objects into * ascending order, according to the * {@linkplain Comparable natural ordering} of its * elements. The range to be sorted extends from index * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All * elements in this range must implement the {@link Comparable} * interface. Furthermore, all elements in this range must be <i>mutually * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a * {@code ClassCastException} for any elements {@code e1} and * {@code e2} in the array). * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will * not be reordered as a result of the sort. * * <p>Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * * <p>The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * * <p>The implementation was adapted from Tim Peters's list sort for Python * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> * TimSort</a>). It uses 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 <i>mutually comparable</i> (for example, strings and * integers).
*/ publicstaticvoid 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. */ privatestaticvoid 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.
*/ privatestaticfinalint 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"}) privatestaticvoid 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].
*/ privatestaticvoid swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
/** * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * <i>mutually comparable</i> by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the array). * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will * not be reordered as a result of the sort. * * <p>Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * * <p>The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * * <p>The implementation was adapted from Tim Peters's list sort for Python * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> * TimSort</a>). It uses 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 <i>mutually comparable</i> using the specified comparator * @throws IllegalArgumentException (optional) if the comparator is * found to violate the {@link Comparator} contract
*/ publicstatic <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. */ privatestatic <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
T[] aux = a.clone(); if (c==null)
mergeSort(aux, a, 0, a.length, 0); else
mergeSort(aux, a, 0, a.length, 0, c);
}
/** * Sorts the specified range of the specified array of objects according * to the order induced by the specified comparator. The range to be * sorted extends from index {@code fromIndex}, inclusive, to index * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the * range to be sorted is empty.) All elements in the range must be * <i>mutually comparable</i> by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the range). * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will * not be reordered as a result of the sort. * * <p>Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * * <p>The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * * <p>The implementation was adapted from Tim Peters's list sort for Python * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> * TimSort</a>). It uses 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 * <i>mutually comparable</i> using the specified comparator. * @throws IllegalArgumentException if {@code fromIndex > toIndex} or * (optional) if the comparator is found to violate the * {@link Comparator} contract * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or * {@code toIndex > a.length}
*/ publicstatic <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. */ privatestatic <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"}) privatestaticvoid 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
*/ publicstatic <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
*/ publicstatic <T> void parallelPrefix(T[] array, int fromIndex,
--> --------------------
--> maximum size reached
--> --------------------
¤ 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.0.33Bemerkung:
(vorverarbeitet)
¤
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.
