< prev index next >
src/java.base/share/classes/java/util/Arrays.java
Print this page
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * 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
@@ -125,41 +125,39 @@
}
}
/*
* Sorting methods. Note that all public "sort" methods take the
- * same form: Performing argument checks if necessary, and then
+ * 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
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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, a.length - 1, null, 0, 0);
+ 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>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,38 +166,36 @@
* @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);
+ DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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, a.length - 1, null, 0, 0);
+ 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>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,38 +204,36 @@
* @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);
+ DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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 - 1, null, 0, 0);
+ 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.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,38 +242,36 @@
* @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);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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 - 1, null, 0, 0);
+ 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.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,38 +280,36 @@
* @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);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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 - 1);
+ 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.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,11 +318,11 @@
* @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);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
@@ -342,20 +332,19 @@
* 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
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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, a.length - 1, null, 0, 0);
+ 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,14 +357,13 @@
* 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
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,11 +372,11 @@
* @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);
+ DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
@@ -398,20 +386,19 @@
* 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
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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, a.length - 1, null, 0, 0);
+ 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,14 +411,13 @@
* 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
+ * @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 many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
+ * 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,59 +426,39 @@
* @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);
+ DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
}
/**
* 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.
+ * @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) {
- 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();
+ 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 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.
+ * @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,67 +468,39 @@
*
* @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();
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* 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.
+ * @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) {
- 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();
+ 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 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.
+ * @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,67 +510,39 @@
*
* @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();
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* 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.
+ * @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) {
- 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();
+ 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 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.
+ * @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,67 +552,39 @@
*
* @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();
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* 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.
+ * @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) {
- 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();
+ 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 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.
+ * @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,67 +594,39 @@
*
* @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();
+ DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
}
/**
* 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.
+ * @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) {
- 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();
+ 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 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.
+ * @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,19 +636,11 @@
*
* @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();
+ DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
@@ -804,35 +650,21 @@
* 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.
+ * @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) {
- 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();
+ 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,20 +677,14 @@
* 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.
+ * @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,19 +694,11 @@
*
* @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();
+ DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
@@ -890,35 +708,21 @@
* 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.
+ * @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) {
- 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();
+ 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,20 +735,14 @@
* 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.
+ * @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,19 +752,11 @@
*
* @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();
+ DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex);
}
/**
* Sorts the specified array of objects into ascending order, according
* to the {@linkplain Comparable natural ordering} of its elements.
@@ -3000,11 +2790,11 @@
* 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>
+ * <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,11 +2823,11 @@
* 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>
+ * <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,11 +2873,11 @@
* 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>
+ * <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,11 +2906,11 @@
* 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>
+ * <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,9 +8709,9 @@
if (v != 0) {
return i;
}
}
}
-
return aLength != bLength ? length : -1;
}
}
+
< prev index next >