jdk-sandbox: comparison src/java.base/share/classes/java/util/Arrays.java

equal deleted inserted replaced

-:d6d8fdc95ed2
+:8910b995a2ee
 * @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() {}
+/*
+* Sorting methods. Note that all public "sort" methods take the
+* same form: performing argument checks if necessary, and then
+* expanding arguments into those required for the internal
+* implementation methods residing in other package-private
+* classes (except for legacyMergeSort, included in this class).
+*/
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*/
+public static void sort(int[] a) {
+DualPivotQuicksort.sort(a, 0, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*/
+public static void sort(int[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*/
+public static void sort(long[] a) {
+DualPivotQuicksort.sort(a, 0, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*/
+public static void sort(long[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*/
+public static void sort(short[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*/
+public static void sort(short[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*/
+public static void sort(char[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*/
+public static void sort(char[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*/
+public static void sort(byte[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort
+* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*/
+public static void sort(byte[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* <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
+*/
+public static void sort(float[] a) {
+DualPivotQuicksort.sort(a, 0, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* <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}
+*/
+public static void sort(float[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* <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
+*/
+public static void sort(double[] a) {
+DualPivotQuicksort.sort(a, 0, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending order. The range
+* to be sorted extends from the index {@code fromIndex}, inclusive, to
+* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+* the range to be sorted is empty.
+*
+* <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}
+*/
+public static void sort(double[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*
+* @since 1.8
+*/
+public static void parallelSort(byte[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*
+* @since 1.8
+*/
+public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*
+* @since 1.8
+*/
+public static void parallelSort(char[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*
+* @since 1.8
+*/
+public static void parallelSort(char[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*
+* @since 1.8
+*/
+public static void parallelSort(short[] a) {
+DualPivotQuicksort.sort(a, 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*
+* @since 1.8
+*/
+public static void parallelSort(short[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*
+* @since 1.8
+*/
+public static void parallelSort(int[] a) {
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*
+* @since 1.8
+*/
+public static void parallelSort(int[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+*
+* @since 1.8
+*/
+public static void parallelSort(long[] a) {
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* @implNote The sorting algorithm is a Dual-Pivot Quicksort by
+* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
+* offers O(n log(n)) performance on all data sets, and is typically
+* faster than traditional (one-pivot) Quicksort implementations.
+*
+* @param a the array to be sorted
+* @param fromIndex the index of the first element, inclusive, to be sorted
+* @param toIndex the index of the last element, exclusive, to be sorted
+*
+* @throws IllegalArgumentException if {@code fromIndex > toIndex}
+* @throws ArrayIndexOutOfBoundsException
+*     if {@code fromIndex < 0} or {@code toIndex > a.length}
+*
+* @since 1.8
+*/
+public static void parallelSort(long[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* <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
+*/
+public static void parallelSort(float[] a) {
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* <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
+*/
+public static void parallelSort(float[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
+}
+/**
+* Sorts the specified array into ascending numerical order.
+*
+* <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
+*/
+public static void parallelSort(double[] a) {
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length);
+}
+/**
+* Sorts the specified range of the array into ascending numerical order.
+* The range to be sorted extends from the index {@code fromIndex},
+* inclusive, to the index {@code toIndex}, exclusive. If
+* {@code fromIndex == toIndex}, the range to be sorted is empty.
+*
+* <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
+*/
+public static void parallelSort(double[] a, int fromIndex, int toIndex) {
+rangeCheck(a.length, fromIndex, toIndex);
+DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
+}
+/**
+* Checks that {@code fromIndex} and {@code toIndex} are in
+* the range and throws an exception if they aren't.
+*/
+static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
+if (fromIndex > toIndex) {
+throw new IllegalArgumentException(
+"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+}
+if (fromIndex < 0) {
+throw new ArrayIndexOutOfBoundsException(fromIndex);
+}
+if (toIndex > arrayLength) {
+throw new ArrayIndexOutOfBoundsException(toIndex);
+}
+}
 /**
 * A comparator that implements the natural ordering of a group of
 * mutually comparable elements. May be used when a supplied
 * comparator is null. To simplify code-sharing within underlying
 }
 static final NaturalOrder INSTANCE = new NaturalOrder();
 }
 /**
-* Checks that {@code fromIndex} and {@code toIndex} are in
+* The minimum array length below which a parallel sorting
-* the range and throws an exception if they aren't.
+* algorithm will not further partition the sorting task. Using
-*/
+* smaller sizes typically results in memory contention across
-static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
+* tasks that makes parallel speedups unlikely.
-if (fromIndex > toIndex) {
+*/
-throw new IllegalArgumentException(
+private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
-"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
-}
-if (fromIndex < 0) {
-throw new ArrayIndexOutOfBoundsException(fromIndex);
-}
-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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*/
-public static void sort(int[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, 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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*/
-public static void sort(long[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, 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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*/
-public static void sort(char[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, 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.
-*
-* <p>The {@code <} relation does not provide a total order on all float
-* values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
-* value compares neither less than, greater than, nor equal to any value,
-* even itself. This method uses the total order imposed by the method
-* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
-* {@code 0.0f} and {@code Float.NaN} is considered greater than any
-* other value and all {@code Float.NaN} values are considered equal.
-*
-* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
-* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-* offers O(n log(n)) performance on many data sets that cause other
-* quicksorts to degrade to quadratic performance, and is typically
-* faster than traditional (one-pivot) Quicksort implementations.
-*
-* @param a the array to be sorted
-*/
-public static void sort(float[] a) {
-DualPivotQuicksort.sort(a, 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>The {@code <} relation does not provide a total order on all float
-* values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
-* value compares neither less than, greater than, nor equal to any value,
-* even itself. This method uses the total order imposed by the method
-* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
-* {@code 0.0f} and {@code Float.NaN} is considered greater than any
-* other value and all {@code Float.NaN} values are considered equal.
-*
-* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
-* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-* offers O(n log(n)) performance on many data sets that cause other
-* quicksorts to degrade to quadratic performance, and is typically
-* faster than traditional (one-pivot) Quicksort implementations.
-*
-* @param a the array to be sorted
-* @param fromIndex the index of the first element, inclusive, to be sorted
-* @param toIndex the index of the last element, exclusive, to be sorted
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*/
-public static void sort(float[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
-}
-/**
-* Sorts the specified array into ascending numerical order.
-*
-* <p>The {@code <} relation does not provide a total order on all double
-* values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
-* value compares neither less than, greater than, nor equal to any value,
-* even itself. This method uses the total order imposed by the method
-* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
-* {@code 0.0d} and {@code Double.NaN} is considered greater than any
-* other value and all {@code Double.NaN} values are considered equal.
-*
-* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
-* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-* offers O(n log(n)) performance on many data sets that cause other
-* quicksorts to degrade to quadratic performance, and is typically
-* faster than traditional (one-pivot) Quicksort implementations.
-*
-* @param a the array to be sorted
-*/
-public static void sort(double[] a) {
-DualPivotQuicksort.sort(a, 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>The {@code <} relation does not provide a total order on all double
-* values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
-* value compares neither less than, greater than, nor equal to any value,
-* even itself. This method uses the total order imposed by the method
-* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
-* {@code 0.0d} and {@code Double.NaN} is considered greater than any
-* other value and all {@code Double.NaN} values are considered equal.
-*
-* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
-* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-* offers O(n log(n)) performance on many data sets that cause other
-* quicksorts to degrade to quadratic performance, and is typically
-* faster than traditional (one-pivot) Quicksort implementations.
-*
-* @param a the array to be sorted
-* @param fromIndex the index of the first element, inclusive, to be sorted
-* @param toIndex the index of the last element, exclusive, to be sorted
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*/
-public static void sort(double[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, 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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(char[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(short[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(int[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(long[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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.
-*
-* <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 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},
-* 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 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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(float[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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.
-*
-* <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 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},
-* 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 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
-*
-* @throws IllegalArgumentException if {@code fromIndex > toIndex}
-* @throws ArrayIndexOutOfBoundsException
-*     if {@code fromIndex < 0} or {@code toIndex > a.length}
-*
-* @since 1.8
-*/
-public static void parallelSort(double[] a, int fromIndex, int toIndex) {
-rangeCheck(a.length, fromIndex, toIndex);
-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}

changeset 59042	8910b995a2ee
parent 58520	e036ee8bae56
child 59055	57ad70bcf06c