< prev index next >
src/java.base/share/classes/java/util/Arrays.java
Print this page
*** 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
--- 1,7 ----
/*
! * Copyright (c) 1997, 2019, 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
*** 72,165 ****
* @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) {
- throw new IllegalArgumentException(
- "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
--- 72,115 ----
* @author John Rose
* @since 1.2
*/
public class Arrays {
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
/*
* Sorting methods. Note that all public "sort" methods take the
! * same form: performing argument checks if necessary, and then
* expanding arguments into those required for the internal
* implementation methods residing in other package-private
* classes (except for legacyMergeSort, included in this class).
*/
/**
* Sorts the specified array into ascending numerical order.
*
! * @implNote The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on all data sets, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
! DualPivotQuicksort.sort(a, 0, 0, a.length);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
! * @implNote The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
! * offers O(n log(n)) performance on all data sets, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
*** 168,205 ****
* @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
--- 118,153 ----
* @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
*** 208,245 ****
* @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
--- 156,191 ----
* @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
*** 248,285 ****
* @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
--- 194,229 ----
* @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
*** 288,325 ****
* @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
--- 232,267 ----
* @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
*** 328,338 ****
* @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.
*
--- 270,280 ----
* @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.
*
*** 342,361 ****
* 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
--- 284,302 ----
* 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
*** 368,381 ****
* 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
--- 309,321 ----
* 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
*** 384,394 ****
* @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.
*
--- 324,334 ----
* @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.
*
*** 398,417 ****
* 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
--- 338,356 ----
* 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
*** 424,437 ****
* 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
--- 363,375 ----
* 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
*** 440,498 ****
* @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
*
--- 378,416 ----
* @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
*
*** 502,568 ****
*
* @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
*
--- 420,458 ----
*
* @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
*
*** 572,638 ****
*
* @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
*
--- 462,500 ----
*
* @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
*
*** 642,708 ****
*
* @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
*
--- 504,542 ----
*
* @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
*
*** 712,778 ****
*
* @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
*
--- 546,584 ----
*
* @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
*
*** 782,800 ****
*
* @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.
*
--- 588,598 ----
*
* @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.
*
*** 804,838 ****
* 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},
--- 602,622 ----
* 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},
*** 845,864 ****
* 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
*
--- 629,642 ----
* 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
*
*** 868,886 ****
*
* @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.
*
--- 646,656 ----
*
* @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.
*
*** 890,924 ****
* 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},
--- 660,680 ----
* 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},
*** 931,950 ****
* 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
*
--- 687,700 ----
* 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
*
*** 954,975 ****
*
* @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
--- 704,765 ----
*
* @since 1.8
*/
public static void parallelSort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
! DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
}
/**
+ * Checks that {@code fromIndex} and {@code toIndex} are in
+ * the range and throws an exception if they aren't.
+ */
+ static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > arrayLength) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
+ }
+
+ /**
+ * A comparator that implements the natural ordering of a group of
+ * mutually comparable elements. May be used when a supplied
+ * comparator is null. To simplify code-sharing within underlying
+ * implementations, the compare method only declares type Object
+ * for its second argument.
+ *
+ * Arrays class implementor's note: It is an empirical matter
+ * whether ComparableTimSort offers any performance benefit over
+ * TimSort used with this comparator. If not, you are better off
+ * deleting or bypassing ComparableTimSort. There is currently no
+ * empirical case for separating them for parallel sorting, so all
+ * public Object parallelSort methods use the same comparator
+ * based implementation.
+ */
+ static final class NaturalOrder implements Comparator<Object> {
+ @SuppressWarnings("unchecked")
+ public int compare(Object first, Object second) {
+ return ((Comparable<Object>)first).compareTo(second);
+ }
+ static final NaturalOrder INSTANCE = new NaturalOrder();
+ }
+
+ /**
+ * The minimum array length below which a parallel sorting
+ * algorithm will not further partition the sorting task. Using
+ * smaller sizes typically results in memory contention across
+ * tasks that makes parallel speedups unlikely.
+ */
+ private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
+
+ /**
* Sorts the specified array of objects into ascending order, according
* to the {@linkplain Comparable natural ordering} of its elements.
* All elements in the array must implement the {@link Comparable}
* interface. Furthermore, all elements in the array must be
* <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
*** 3000,3010 ****
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are {@code null}.
*
* Two doubles {@code d1} and {@code d2} are considered equal if:
! * <pre> {@code new Double(d1).equals(new Double(d2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
--- 2790,2800 ----
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are {@code null}.
*
* Two doubles {@code d1} and {@code d2} are considered equal if:
! * <pre>{@code new Double(d1).equals(new Double(d2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
*** 3033,3043 ****
* specified ranges in the two arrays are equal. In other words, two arrays
* are equal if they contain, over the specified ranges, the same elements
* in the same order.
*
* <p>Two doubles {@code d1} and {@code d2} are considered equal if:
! * <pre> {@code new Double(d1).equals(new Double(d2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
*
* @param a the first array to be tested for equality
* @param aFromIndex the index (inclusive) of the first element in the
--- 2823,2833 ----
* specified ranges in the two arrays are equal. In other words, two arrays
* are equal if they contain, over the specified ranges, the same elements
* in the same order.
*
* <p>Two doubles {@code d1} and {@code d2} are considered equal if:
! * <pre>{@code new Double(d1).equals(new Double(d2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0d unequal to -0.0d.)
*
* @param a the first array to be tested for equality
* @param aFromIndex the index (inclusive) of the first element in the
*** 3083,3093 ****
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are {@code null}.
*
* Two floats {@code f1} and {@code f2} are considered equal if:
! * <pre> {@code new Float(f1).equals(new Float(f2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
--- 2873,2883 ----
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are {@code null}.
*
* Two floats {@code f1} and {@code f2} are considered equal if:
! * <pre>{@code new Float(f1).equals(new Float(f2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
*** 3116,3126 ****
* specified ranges in the two arrays are equal. In other words, two arrays
* are equal if they contain, over the specified ranges, the same elements
* in the same order.
*
* <p>Two floats {@code f1} and {@code f2} are considered equal if:
! * <pre> {@code new Float(f1).equals(new Float(f2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
*
* @param a the first array to be tested for equality
* @param aFromIndex the index (inclusive) of the first element in the
--- 2906,2916 ----
* specified ranges in the two arrays are equal. In other words, two arrays
* are equal if they contain, over the specified ranges, the same elements
* in the same order.
*
* <p>Two floats {@code f1} and {@code f2} are considered equal if:
! * <pre>{@code new Float(f1).equals(new Float(f2))}</pre>
* (Unlike the {@code ==} operator, this method considers
* {@code NaN} equals to itself, and 0.0f unequal to -0.0f.)
*
* @param a the first array to be tested for equality
* @param aFromIndex the index (inclusive) of the first element in the
*** 8919,8927 ****
if (v != 0) {
return i;
}
}
}
-
return aLength != bLength ? length : -1;
}
}
--- 8709,8716 ----
< prev index next >