< prev index next >
src/java.base/share/classes/java/util/Arrays.java
Print this page
*** 1,7 ****
/*
! * Copyright (c) 1997, 2016, 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
--- 1,7 ----
/*
! * Copyright (c) 1997, 2018, 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
*** 61,115 ****
* 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/util/package-summary.html#CollectionsFramework">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @author John Rose
* @since 1.2
*/
public class Arrays {
- /**
- * 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;
-
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
/**
- * 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();
- }
-
- /**
* 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) {
--- 61,84 ----
* algorithms, so long as the specification itself is adhered to. (For
* example, the algorithm used by {@code sort(Object[])} does not have to be
* a MergeSort, but it does have to be <i>stable</i>.)
*
* <p>This class is a member of the
! * <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @author John Rose
* @since 1.2
*/
public class Arrays {
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
/**
* 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) {
*** 122,164 ****
if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
/*
* 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.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
--- 91,137 ----
if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
+ /**
+ * This flag allows system to run sorting in parallel.
+ */
+ private static final boolean RUN_IN_PARALLEL =
+ Runtime.getRuntime().availableProcessors() > 1;
+
/*
* 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 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
*/
public static void sort(int[] a) {
! DualPivotQuicksort.sort(a, false, 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 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
*** 167,204 ****
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(long[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
--- 140,175 ----
* @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, false, 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
*/
public static void sort(long[] a) {
! DualPivotQuicksort.sort(a, false, 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 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
*** 207,284 ****
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
! public static void sort(short[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
*
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
! public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(char[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
--- 178,251 ----
* @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, false, 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
*/
! public static void sort(byte[] a) {
! DualPivotQuicksort.sort(a, false, 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 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}
*/
! public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, false, 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
*/
public static void sort(char[] a) {
! DualPivotQuicksort.sort(a, false, 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 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
*** 287,337 ****
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
! public static void sort(byte[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
*
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
! public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}
/**
* Sorts the specified array into ascending numerical order.
*
--- 254,302 ----
* @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, false, 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
*/
! public static void sort(short[] a) {
! DualPivotQuicksort.sort(a, false, 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 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}
*/
! public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
*** 341,360 ****
* even itself. This method uses the total order imposed by the method
* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
* {@code 0.0f} and {@code Float.NaN} is considered greater than any
* other value and all {@code Float.NaN} values are considered equal.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(float[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
--- 306,324 ----
* 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
*/
public static void sort(float[] a) {
! DualPivotQuicksort.sort(a, false, 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
*** 367,380 ****
* even itself. This method uses the total order imposed by the method
* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
* {@code 0.0f} and {@code Float.NaN} is considered greater than any
* other value and all {@code Float.NaN} values are considered equal.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
--- 331,343 ----
* 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
*** 383,393 ****
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
--- 346,356 ----
* @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, false, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
*** 397,416 ****
* even itself. This method uses the total order imposed by the method
* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
* {@code 0.0d} and {@code Double.NaN} is considered greater than any
* other value and all {@code Double.NaN} values are considered equal.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(double[] a) {
! DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
--- 360,378 ----
* 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
*/
public static void sort(double[] a) {
! DualPivotQuicksort.sort(a, false, 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
*** 423,436 ****
* even itself. This method uses the total order imposed by the method
* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
* {@code 0.0d} and {@code Double.NaN} is considered greater than any
* other value and all {@code Double.NaN} values are considered equal.
*
! * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
! * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on many data sets that cause other
! * quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
--- 385,397 ----
* 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
*** 439,497 ****
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
* Sorts the specified array into ascending numerical order.
*
! * @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(byte[]) 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(byte[]) 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 a the array to be sorted
*
* @since 1.8
*/
! public static void parallelSort(byte[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1);
! else
! new ArraysParallelSortHelpers.FJByte.Sorter
! (null, a, new byte[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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 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(byte[]) 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(byte[]) 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 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
*
--- 400,438 ----
* @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, false, 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, RUN_IN_PARALLEL, 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
*
*** 499,567 ****
* @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);
! int n = toIndex - fromIndex, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
! else
! new ArraysParallelSortHelpers.FJByte.Sorter
! (null, a, new byte[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
! * @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(char[]) 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(char[]) 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 a the array to be sorted
*
* @since 1.8
*/
! public static void parallelSort(char[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJChar.Sorter
! (null, a, new char[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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 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(char[]) 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(char[]) 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 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
*
--- 440,480 ----
* @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, RUN_IN_PARALLEL, 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, RUN_IN_PARALLEL, 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
*
*** 569,637 ****
* @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);
! int n = toIndex - fromIndex, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJChar.Sorter
! (null, a, new char[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
! * @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(short[]) 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(short[]) 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 a the array to be sorted
*
* @since 1.8
*/
! public static void parallelSort(short[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJShort.Sorter
! (null, a, new short[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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 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(short[]) 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(short[]) 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 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
*
--- 482,522 ----
* @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, RUN_IN_PARALLEL, 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, RUN_IN_PARALLEL, 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
*
*** 639,707 ****
* @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);
! int n = toIndex - fromIndex, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJShort.Sorter
! (null, a, new short[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
! * @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(int[]) 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(int[]) 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 a the array to be sorted
*
* @since 1.8
*/
! public static void parallelSort(int[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJInt.Sorter
! (null, a, new int[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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 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(int[]) 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(int[]) 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 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
*
--- 524,564 ----
* @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, RUN_IN_PARALLEL, 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, RUN_IN_PARALLEL, 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
*
*** 709,777 ****
* @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);
! int n = toIndex - fromIndex, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJInt.Sorter
! (null, a, new int[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
! * @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(long[]) 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(long[]) 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 a the array to be sorted
*
* @since 1.8
*/
! public static void parallelSort(long[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJLong.Sorter
! (null, a, new long[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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 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(long[]) 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(long[]) 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 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
*
--- 566,606 ----
* @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, RUN_IN_PARALLEL, 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, RUN_IN_PARALLEL, 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
*
*** 779,799 ****
* @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);
! int n = toIndex - fromIndex, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJLong.Sorter
! (null, a, new long[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
--- 608,620 ----
* @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, RUN_IN_PARALLEL, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
*** 803,837 ****
* 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 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(float[]) 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(float[]) 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 a the array to be sorted
*
* @since 1.8
*/
public static void parallelSort(float[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJFloat.Sorter
! (null, a, new float[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified range of the array into ascending numerical order.
* The range to be sorted extends from the index {@code fromIndex},
--- 624,644 ----
* 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, RUN_IN_PARALLEL, 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},
*** 844,863 ****
* 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 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(float[]) 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(float[]) 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 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
*
--- 651,664 ----
* 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
*
*** 867,885 ****
*
* @since 1.8
*/
public static void parallelSort(float[] 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)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJFloat.Sorter
! (null, a, new float[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified array into ascending numerical order.
*
--- 668,678 ----
*
* @since 1.8
*/
public static void parallelSort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
*** 889,923 ****
* 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 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(double[]) 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(double[]) 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 a the array to be sorted
*
* @since 1.8
*/
public static void parallelSort(double[] a) {
! int n = a.length, p, g;
! if (n <= MIN_ARRAY_SORT_GRAN ||
! (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
! DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJDouble.Sorter
! (null, a, new double[n], 0, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* Sorts the specified range of the array into ascending numerical order.
* The range to be sorted extends from the index {@code fromIndex},
--- 682,702 ----
* 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, RUN_IN_PARALLEL, 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},
*** 930,949 ****
* 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 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(double[]) 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(double[]) 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 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
*
--- 709,722 ----
* 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
*
*** 953,974 ****
*
* @since 1.8
*/
public static void parallelSort(double[] 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)
! DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
! else
! new ArraysParallelSortHelpers.FJDouble.Sorter
! (null, a, new double[n], fromIndex, n, 0,
! ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
! MIN_ARRAY_SORT_GRAN : g).invoke();
}
/**
* 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
--- 726,770 ----
*
* @since 1.8
*/
public static void parallelSort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, 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
* <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
< prev index next >