1 /*
2 * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
46 import java.util.stream.Stream;
47 import java.util.stream.StreamSupport;
48
49 /**
50 * This class contains various methods for manipulating arrays (such as
51 * sorting and searching). This class also contains a static factory
52 * that allows arrays to be viewed as lists.
53 *
54 * <p>The methods in this class all throw a {@code NullPointerException},
55 * if the specified array reference is null, except where noted.
56 *
57 * <p>The documentation for the methods contained in this class includes
58 * brief descriptions of the <i>implementations</i>. Such descriptions should
59 * be regarded as <i>implementation notes</i>, rather than parts of the
60 * <i>specification</i>. Implementors should feel free to substitute other
61 * algorithms, so long as the specification itself is adhered to. (For
62 * example, the algorithm used by {@code sort(Object[])} does not have to be
63 * a MergeSort, but it does have to be <i>stable</i>.)
64 *
65 * <p>This class is a member of the
66 * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
67 * Java Collections Framework</a>.
68 *
69 * @author Josh Bloch
70 * @author Neal Gafter
71 * @author John Rose
72 * @since 1.2
73 */
74 public class Arrays {
75
76 /**
77 * The minimum array length below which a parallel sorting
78 * algorithm will not further partition the sorting task. Using
79 * smaller sizes typically results in memory contention across
80 * tasks that makes parallel speedups unlikely.
81 */
82 private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
83
84 // Suppresses default constructor, ensuring non-instantiability.
85 private Arrays() {}
86
87 /**
88 * A comparator that implements the natural ordering of a group of
89 * mutually comparable elements. May be used when a supplied
90 * comparator is null. To simplify code-sharing within underlying
91 * implementations, the compare method only declares type Object
92 * for its second argument.
93 *
94 * Arrays class implementor's note: It is an empirical matter
95 * whether ComparableTimSort offers any performance benefit over
96 * TimSort used with this comparator. If not, you are better off
97 * deleting or bypassing ComparableTimSort. There is currently no
98 * empirical case for separating them for parallel sorting, so all
99 * public Object parallelSort methods use the same comparator
100 * based implementation.
101 */
102 static final class NaturalOrder implements Comparator<Object> {
103 @SuppressWarnings("unchecked")
104 public int compare(Object first, Object second) {
105 return ((Comparable<Object>)first).compareTo(second);
106 }
107 static final NaturalOrder INSTANCE = new NaturalOrder();
108 }
109
110 /**
111 * Checks that {@code fromIndex} and {@code toIndex} are in
112 * the range and throws an exception if they aren't.
113 */
114 static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
115 if (fromIndex > toIndex) {
116 throw new IllegalArgumentException(
117 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
118 }
119 if (fromIndex < 0) {
120 throw new ArrayIndexOutOfBoundsException(fromIndex);
121 }
122 if (toIndex > arrayLength) {
123 throw new ArrayIndexOutOfBoundsException(toIndex);
124 }
125 }
126
127 /*
128 * Sorting methods. Note that all public "sort" methods take the
129 * same form: Performing argument checks if necessary, and then
130 * expanding arguments into those required for the internal
131 * implementation methods residing in other package-private
132 * classes (except for legacyMergeSort, included in this class).
133 */
134
135 /**
136 * Sorts the specified array into ascending numerical order.
137 *
138 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
139 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
140 * offers O(n log(n)) performance on many data sets that cause other
141 * quicksorts to degrade to quadratic performance, and is typically
142 * faster than traditional (one-pivot) Quicksort implementations.
143 *
144 * @param a the array to be sorted
145 */
146 public static void sort(int[] a) {
147 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
148 }
149
150 /**
151 * Sorts the specified range of the array into ascending order. The range
152 * to be sorted extends from the index {@code fromIndex}, inclusive, to
153 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
154 * the range to be sorted is empty.
155 *
156 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
157 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
158 * offers O(n log(n)) performance on many data sets that cause other
159 * quicksorts to degrade to quadratic performance, and is typically
160 * faster than traditional (one-pivot) Quicksort implementations.
161 *
162 * @param a the array to be sorted
163 * @param fromIndex the index of the first element, inclusive, to be sorted
164 * @param toIndex the index of the last element, exclusive, to be sorted
165 *
166 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
167 * @throws ArrayIndexOutOfBoundsException
168 * if {@code fromIndex < 0} or {@code toIndex > a.length}
169 */
170 public static void sort(int[] a, int fromIndex, int toIndex) {
171 rangeCheck(a.length, fromIndex, toIndex);
172 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
173 }
174
175 /**
176 * Sorts the specified array into ascending numerical order.
177 *
178 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
179 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
180 * offers O(n log(n)) performance on many data sets that cause other
181 * quicksorts to degrade to quadratic performance, and is typically
182 * faster than traditional (one-pivot) Quicksort implementations.
183 *
184 * @param a the array to be sorted
185 */
186 public static void sort(long[] a) {
187 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
188 }
189
190 /**
191 * Sorts the specified range of the array into ascending order. The range
192 * to be sorted extends from the index {@code fromIndex}, inclusive, to
193 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
194 * the range to be sorted is empty.
195 *
196 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
197 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
198 * offers O(n log(n)) performance on many data sets that cause other
199 * quicksorts to degrade to quadratic performance, and is typically
200 * faster than traditional (one-pivot) Quicksort implementations.
201 *
202 * @param a the array to be sorted
203 * @param fromIndex the index of the first element, inclusive, to be sorted
204 * @param toIndex the index of the last element, exclusive, to be sorted
205 *
206 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
207 * @throws ArrayIndexOutOfBoundsException
208 * if {@code fromIndex < 0} or {@code toIndex > a.length}
209 */
210 public static void sort(long[] a, int fromIndex, int toIndex) {
211 rangeCheck(a.length, fromIndex, toIndex);
212 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
213 }
214
215 /**
216 * Sorts the specified array into ascending numerical order.
217 *
218 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
219 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
220 * offers O(n log(n)) performance on many data sets that cause other
221 * quicksorts to degrade to quadratic performance, and is typically
222 * faster than traditional (one-pivot) Quicksort implementations.
223 *
224 * @param a the array to be sorted
225 */
226 public static void sort(short[] a) {
227 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
228 }
229
230 /**
231 * Sorts the specified range of the array into ascending order. The range
232 * to be sorted extends from the index {@code fromIndex}, inclusive, to
233 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
234 * the range to be sorted is empty.
235 *
236 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
237 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
238 * offers O(n log(n)) performance on many data sets that cause other
239 * quicksorts to degrade to quadratic performance, and is typically
240 * faster than traditional (one-pivot) Quicksort implementations.
241 *
242 * @param a the array to be sorted
243 * @param fromIndex the index of the first element, inclusive, to be sorted
244 * @param toIndex the index of the last element, exclusive, to be sorted
245 *
246 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
247 * @throws ArrayIndexOutOfBoundsException
248 * if {@code fromIndex < 0} or {@code toIndex > a.length}
249 */
250 public static void sort(short[] a, int fromIndex, int toIndex) {
251 rangeCheck(a.length, fromIndex, toIndex);
252 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
253 }
254
255 /**
256 * Sorts the specified array into ascending numerical order.
257 *
258 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
259 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
260 * offers O(n log(n)) performance on many data sets that cause other
261 * quicksorts to degrade to quadratic performance, and is typically
262 * faster than traditional (one-pivot) Quicksort implementations.
263 *
264 * @param a the array to be sorted
265 */
266 public static void sort(char[] a) {
267 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
268 }
269
270 /**
271 * Sorts the specified range of the array into ascending order. The range
272 * to be sorted extends from the index {@code fromIndex}, inclusive, to
273 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
274 * the range to be sorted is empty.
275 *
276 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
277 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
278 * offers O(n log(n)) performance on many data sets that cause other
279 * quicksorts to degrade to quadratic performance, and is typically
280 * faster than traditional (one-pivot) Quicksort implementations.
281 *
282 * @param a the array to be sorted
283 * @param fromIndex the index of the first element, inclusive, to be sorted
284 * @param toIndex the index of the last element, exclusive, to be sorted
285 *
286 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
287 * @throws ArrayIndexOutOfBoundsException
288 * if {@code fromIndex < 0} or {@code toIndex > a.length}
289 */
290 public static void sort(char[] a, int fromIndex, int toIndex) {
291 rangeCheck(a.length, fromIndex, toIndex);
292 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
293 }
294
295 /**
296 * Sorts the specified array into ascending numerical order.
297 *
298 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
299 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
300 * offers O(n log(n)) performance on many data sets that cause other
301 * quicksorts to degrade to quadratic performance, and is typically
302 * faster than traditional (one-pivot) Quicksort implementations.
303 *
304 * @param a the array to be sorted
305 */
306 public static void sort(byte[] a) {
307 DualPivotQuicksort.sort(a, 0, a.length - 1);
308 }
309
310 /**
311 * Sorts the specified range of the array into ascending order. The range
312 * to be sorted extends from the index {@code fromIndex}, inclusive, to
313 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
314 * the range to be sorted is empty.
315 *
316 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
317 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
318 * offers O(n log(n)) performance on many data sets that cause other
319 * quicksorts to degrade to quadratic performance, and is typically
320 * faster than traditional (one-pivot) Quicksort implementations.
321 *
322 * @param a the array to be sorted
323 * @param fromIndex the index of the first element, inclusive, to be sorted
324 * @param toIndex the index of the last element, exclusive, to be sorted
325 *
326 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
327 * @throws ArrayIndexOutOfBoundsException
328 * if {@code fromIndex < 0} or {@code toIndex > a.length}
329 */
330 public static void sort(byte[] a, int fromIndex, int toIndex) {
331 rangeCheck(a.length, fromIndex, toIndex);
332 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
333 }
334
335 /**
336 * Sorts the specified array into ascending numerical order.
337 *
338 * <p>The {@code <} relation does not provide a total order on all float
339 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
340 * value compares neither less than, greater than, nor equal to any value,
341 * even itself. This method uses the total order imposed by the method
342 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
343 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
344 * other value and all {@code Float.NaN} values are considered equal.
345 *
346 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
347 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
348 * offers O(n log(n)) performance on many data sets that cause other
349 * quicksorts to degrade to quadratic performance, and is typically
350 * faster than traditional (one-pivot) Quicksort implementations.
351 *
352 * @param a the array to be sorted
353 */
354 public static void sort(float[] a) {
355 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
356 }
357
358 /**
359 * Sorts the specified range of the array into ascending order. The range
360 * to be sorted extends from the index {@code fromIndex}, inclusive, to
361 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
362 * the range to be sorted is empty.
363 *
364 * <p>The {@code <} relation does not provide a total order on all float
365 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
366 * value compares neither less than, greater than, nor equal to any value,
367 * even itself. This method uses the total order imposed by the method
368 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
369 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
370 * other value and all {@code Float.NaN} values are considered equal.
371 *
372 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
373 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
374 * offers O(n log(n)) performance on many data sets that cause other
375 * quicksorts to degrade to quadratic performance, and is typically
376 * faster than traditional (one-pivot) Quicksort implementations.
377 *
378 * @param a the array to be sorted
379 * @param fromIndex the index of the first element, inclusive, to be sorted
380 * @param toIndex the index of the last element, exclusive, to be sorted
381 *
382 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
383 * @throws ArrayIndexOutOfBoundsException
384 * if {@code fromIndex < 0} or {@code toIndex > a.length}
385 */
386 public static void sort(float[] a, int fromIndex, int toIndex) {
387 rangeCheck(a.length, fromIndex, toIndex);
388 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
389 }
390
391 /**
392 * Sorts the specified array into ascending numerical order.
393 *
394 * <p>The {@code <} relation does not provide a total order on all double
395 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
396 * value compares neither less than, greater than, nor equal to any value,
397 * even itself. This method uses the total order imposed by the method
398 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
399 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
400 * other value and all {@code Double.NaN} values are considered equal.
401 *
402 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
403 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
404 * offers O(n log(n)) performance on many data sets that cause other
405 * quicksorts to degrade to quadratic performance, and is typically
406 * faster than traditional (one-pivot) Quicksort implementations.
407 *
408 * @param a the array to be sorted
409 */
410 public static void sort(double[] a) {
411 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
412 }
413
414 /**
415 * Sorts the specified range of the array into ascending order. The range
416 * to be sorted extends from the index {@code fromIndex}, inclusive, to
417 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
418 * the range to be sorted is empty.
419 *
420 * <p>The {@code <} relation does not provide a total order on all double
421 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
422 * value compares neither less than, greater than, nor equal to any value,
423 * even itself. This method uses the total order imposed by the method
424 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
425 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
426 * other value and all {@code Double.NaN} values are considered equal.
427 *
428 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
429 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
430 * offers O(n log(n)) performance on many data sets that cause other
431 * quicksorts to degrade to quadratic performance, and is typically
432 * faster than traditional (one-pivot) Quicksort implementations.
433 *
434 * @param a the array to be sorted
435 * @param fromIndex the index of the first element, inclusive, to be sorted
436 * @param toIndex the index of the last element, exclusive, to be sorted
437 *
438 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
439 * @throws ArrayIndexOutOfBoundsException
440 * if {@code fromIndex < 0} or {@code toIndex > a.length}
441 */
442 public static void sort(double[] a, int fromIndex, int toIndex) {
443 rangeCheck(a.length, fromIndex, toIndex);
444 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
445 }
446
447 /**
448 * Sorts the specified array into ascending numerical order.
449 *
450 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
451 * array into sub-arrays that are themselves sorted and then merged. When
452 * the sub-array length reaches a minimum granularity, the sub-array is
453 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}
454 * method. If the length of the specified array is less than the minimum
455 * granularity, then it is sorted using the appropriate {@link
456 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a
457 * working space no greater than the size of the original array. The
458 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
459 * execute any parallel tasks.
460 *
461 * @param a the array to be sorted
462 *
463 * @since 1.8
464 */
465 public static void parallelSort(byte[] a) {
466 int n = a.length, p, g;
467 if (n <= MIN_ARRAY_SORT_GRAN ||
468 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
469 DualPivotQuicksort.sort(a, 0, n - 1);
470 else
471 new ArraysParallelSortHelpers.FJByte.Sorter
472 (null, a, new byte[n], 0, n, 0,
473 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
474 MIN_ARRAY_SORT_GRAN : g).invoke();
475 }
476
477 /**
478 * Sorts the specified range of the array into ascending numerical order.
479 * The range to be sorted extends from the index {@code fromIndex},
480 * inclusive, to the index {@code toIndex}, exclusive. If
481 * {@code fromIndex == toIndex}, the range to be sorted is empty.
482 *
483 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
484 * array into sub-arrays that are themselves sorted and then merged. When
485 * the sub-array length reaches a minimum granularity, the sub-array is
486 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}
487 * method. If the length of the specified array is less than the minimum
488 * granularity, then it is sorted using the appropriate {@link
489 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a working
490 * space no greater than the size of the specified range of the original
491 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
492 * used to execute any parallel tasks.
493 *
494 * @param a the array to be sorted
495 * @param fromIndex the index of the first element, inclusive, to be sorted
496 * @param toIndex the index of the last element, exclusive, to be sorted
497 *
498 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
499 * @throws ArrayIndexOutOfBoundsException
500 * if {@code fromIndex < 0} or {@code toIndex > a.length}
501 *
502 * @since 1.8
503 */
504 public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
505 rangeCheck(a.length, fromIndex, toIndex);
506 int n = toIndex - fromIndex, p, g;
507 if (n <= MIN_ARRAY_SORT_GRAN ||
508 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
509 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
510 else
511 new ArraysParallelSortHelpers.FJByte.Sorter
512 (null, a, new byte[n], fromIndex, n, 0,
513 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
514 MIN_ARRAY_SORT_GRAN : g).invoke();
515 }
516
517 /**
518 * Sorts the specified array into ascending numerical order.
519 *
520 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
521 * array into sub-arrays that are themselves sorted and then merged. When
522 * the sub-array length reaches a minimum granularity, the sub-array is
523 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort}
524 * method. If the length of the specified array is less than the minimum
525 * granularity, then it is sorted using the appropriate {@link
526 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a
527 * working space no greater than the size of the original array. The
528 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
529 * execute any parallel tasks.
530 *
531 * @param a the array to be sorted
532 *
533 * @since 1.8
534 */
535 public static void parallelSort(char[] a) {
536 int n = a.length, p, g;
537 if (n <= MIN_ARRAY_SORT_GRAN ||
538 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
539 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
540 else
541 new ArraysParallelSortHelpers.FJChar.Sorter
542 (null, a, new char[n], 0, n, 0,
543 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
544 MIN_ARRAY_SORT_GRAN : g).invoke();
545 }
546
547 /**
548 * Sorts the specified range of the array into ascending numerical order.
549 * The range to be sorted extends from the index {@code fromIndex},
550 * inclusive, to the index {@code toIndex}, exclusive. If
551 * {@code fromIndex == toIndex}, the range to be sorted is empty.
552 *
553 @implNote The sorting algorithm is a parallel sort-merge that breaks the
554 * array into sub-arrays that are themselves sorted and then merged. When
555 * the sub-array length reaches a minimum granularity, the sub-array is
556 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort}
557 * method. If the length of the specified array is less than the minimum
558 * granularity, then it is sorted using the appropriate {@link
559 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a working
560 * space no greater than the size of the specified range of the original
561 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
562 * used to execute any parallel tasks.
563 *
564 * @param a the array to be sorted
565 * @param fromIndex the index of the first element, inclusive, to be sorted
566 * @param toIndex the index of the last element, exclusive, to be sorted
567 *
568 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
569 * @throws ArrayIndexOutOfBoundsException
570 * if {@code fromIndex < 0} or {@code toIndex > a.length}
571 *
572 * @since 1.8
573 */
574 public static void parallelSort(char[] a, int fromIndex, int toIndex) {
575 rangeCheck(a.length, fromIndex, toIndex);
576 int n = toIndex - fromIndex, p, g;
577 if (n <= MIN_ARRAY_SORT_GRAN ||
578 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
579 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
580 else
581 new ArraysParallelSortHelpers.FJChar.Sorter
582 (null, a, new char[n], fromIndex, n, 0,
583 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
584 MIN_ARRAY_SORT_GRAN : g).invoke();
585 }
586
587 /**
588 * Sorts the specified array into ascending numerical order.
589 *
590 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
591 * array into sub-arrays that are themselves sorted and then merged. When
592 * the sub-array length reaches a minimum granularity, the sub-array is
593 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort}
594 * method. If the length of the specified array is less than the minimum
595 * granularity, then it is sorted using the appropriate {@link
596 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a
597 * working space no greater than the size of the original array. The
598 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
599 * execute any parallel tasks.
600 *
601 * @param a the array to be sorted
602 *
603 * @since 1.8
604 */
605 public static void parallelSort(short[] a) {
606 int n = a.length, p, g;
607 if (n <= MIN_ARRAY_SORT_GRAN ||
608 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
609 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
610 else
611 new ArraysParallelSortHelpers.FJShort.Sorter
612 (null, a, new short[n], 0, n, 0,
613 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
614 MIN_ARRAY_SORT_GRAN : g).invoke();
615 }
616
617 /**
618 * Sorts the specified range of the array into ascending numerical order.
619 * The range to be sorted extends from the index {@code fromIndex},
620 * inclusive, to the index {@code toIndex}, exclusive. If
621 * {@code fromIndex == toIndex}, the range to be sorted is empty.
622 *
623 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
624 * array into sub-arrays that are themselves sorted and then merged. When
625 * the sub-array length reaches a minimum granularity, the sub-array is
626 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort}
627 * method. If the length of the specified array is less than the minimum
628 * granularity, then it is sorted using the appropriate {@link
629 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a working
630 * space no greater than the size of the specified range of the original
631 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
632 * used to execute any parallel tasks.
633 *
634 * @param a the array to be sorted
635 * @param fromIndex the index of the first element, inclusive, to be sorted
636 * @param toIndex the index of the last element, exclusive, to be sorted
637 *
638 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
639 * @throws ArrayIndexOutOfBoundsException
640 * if {@code fromIndex < 0} or {@code toIndex > a.length}
641 *
642 * @since 1.8
643 */
644 public static void parallelSort(short[] a, int fromIndex, int toIndex) {
645 rangeCheck(a.length, fromIndex, toIndex);
646 int n = toIndex - fromIndex, p, g;
647 if (n <= MIN_ARRAY_SORT_GRAN ||
648 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
649 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
650 else
651 new ArraysParallelSortHelpers.FJShort.Sorter
652 (null, a, new short[n], fromIndex, n, 0,
653 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
654 MIN_ARRAY_SORT_GRAN : g).invoke();
655 }
656
657 /**
658 * Sorts the specified array into ascending numerical order.
659 *
660 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
661 * array into sub-arrays that are themselves sorted and then merged. When
662 * the sub-array length reaches a minimum granularity, the sub-array is
663 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort}
664 * method. If the length of the specified array is less than the minimum
665 * granularity, then it is sorted using the appropriate {@link
666 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a
667 * working space no greater than the size of the original array. The
668 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
669 * execute any parallel tasks.
670 *
671 * @param a the array to be sorted
672 *
673 * @since 1.8
674 */
675 public static void parallelSort(int[] a) {
676 int n = a.length, p, g;
677 if (n <= MIN_ARRAY_SORT_GRAN ||
678 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
679 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
680 else
681 new ArraysParallelSortHelpers.FJInt.Sorter
682 (null, a, new int[n], 0, n, 0,
683 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
684 MIN_ARRAY_SORT_GRAN : g).invoke();
685 }
686
687 /**
688 * Sorts the specified range of the array into ascending numerical order.
689 * The range to be sorted extends from the index {@code fromIndex},
690 * inclusive, to the index {@code toIndex}, exclusive. If
691 * {@code fromIndex == toIndex}, the range to be sorted is empty.
692 *
693 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
694 * array into sub-arrays that are themselves sorted and then merged. When
695 * the sub-array length reaches a minimum granularity, the sub-array is
696 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort}
697 * method. If the length of the specified array is less than the minimum
698 * granularity, then it is sorted using the appropriate {@link
699 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a working
700 * space no greater than the size of the specified range of the original
701 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
702 * used to execute any parallel tasks.
703 *
704 * @param a the array to be sorted
705 * @param fromIndex the index of the first element, inclusive, to be sorted
706 * @param toIndex the index of the last element, exclusive, to be sorted
707 *
708 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
709 * @throws ArrayIndexOutOfBoundsException
710 * if {@code fromIndex < 0} or {@code toIndex > a.length}
711 *
712 * @since 1.8
713 */
714 public static void parallelSort(int[] a, int fromIndex, int toIndex) {
715 rangeCheck(a.length, fromIndex, toIndex);
716 int n = toIndex - fromIndex, p, g;
717 if (n <= MIN_ARRAY_SORT_GRAN ||
718 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
719 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
720 else
721 new ArraysParallelSortHelpers.FJInt.Sorter
722 (null, a, new int[n], fromIndex, n, 0,
723 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
724 MIN_ARRAY_SORT_GRAN : g).invoke();
725 }
726
727 /**
728 * Sorts the specified array into ascending numerical order.
729 *
730 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
731 * array into sub-arrays that are themselves sorted and then merged. When
732 * the sub-array length reaches a minimum granularity, the sub-array is
733 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort}
734 * method. If the length of the specified array is less than the minimum
735 * granularity, then it is sorted using the appropriate {@link
736 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a
737 * working space no greater than the size of the original array. The
738 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
739 * execute any parallel tasks.
740 *
741 * @param a the array to be sorted
742 *
743 * @since 1.8
744 */
745 public static void parallelSort(long[] a) {
746 int n = a.length, p, g;
747 if (n <= MIN_ARRAY_SORT_GRAN ||
748 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
749 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
750 else
751 new ArraysParallelSortHelpers.FJLong.Sorter
752 (null, a, new long[n], 0, n, 0,
753 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
754 MIN_ARRAY_SORT_GRAN : g).invoke();
755 }
756
757 /**
758 * Sorts the specified range of the array into ascending numerical order.
759 * The range to be sorted extends from the index {@code fromIndex},
760 * inclusive, to the index {@code toIndex}, exclusive. If
761 * {@code fromIndex == toIndex}, the range to be sorted is empty.
762 *
763 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
764 * array into sub-arrays that are themselves sorted and then merged. When
765 * the sub-array length reaches a minimum granularity, the sub-array is
766 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort}
767 * method. If the length of the specified array is less than the minimum
768 * granularity, then it is sorted using the appropriate {@link
769 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a working
770 * space no greater than the size of the specified range of the original
771 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
772 * used to execute any parallel tasks.
773 *
774 * @param a the array to be sorted
775 * @param fromIndex the index of the first element, inclusive, to be sorted
776 * @param toIndex the index of the last element, exclusive, to be sorted
777 *
778 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
779 * @throws ArrayIndexOutOfBoundsException
780 * if {@code fromIndex < 0} or {@code toIndex > a.length}
781 *
782 * @since 1.8
783 */
784 public static void parallelSort(long[] a, int fromIndex, int toIndex) {
785 rangeCheck(a.length, fromIndex, toIndex);
786 int n = toIndex - fromIndex, p, g;
787 if (n <= MIN_ARRAY_SORT_GRAN ||
788 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
789 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
790 else
791 new ArraysParallelSortHelpers.FJLong.Sorter
792 (null, a, new long[n], fromIndex, n, 0,
793 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
794 MIN_ARRAY_SORT_GRAN : g).invoke();
795 }
796
797 /**
798 * Sorts the specified array into ascending numerical order.
799 *
800 * <p>The {@code <} relation does not provide a total order on all float
801 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
802 * value compares neither less than, greater than, nor equal to any value,
803 * even itself. This method uses the total order imposed by the method
804 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
805 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
806 * other value and all {@code Float.NaN} values are considered equal.
807 *
808 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
809 * array into sub-arrays that are themselves sorted and then merged. When
810 * the sub-array length reaches a minimum granularity, the sub-array is
811 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort}
812 * method. If the length of the specified array is less than the minimum
813 * granularity, then it is sorted using the appropriate {@link
814 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a
815 * working space no greater than the size of the original array. The
816 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
817 * execute any parallel tasks.
818 *
819 * @param a the array to be sorted
820 *
821 * @since 1.8
822 */
823 public static void parallelSort(float[] a) {
824 int n = a.length, p, g;
825 if (n <= MIN_ARRAY_SORT_GRAN ||
826 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
827 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
828 else
829 new ArraysParallelSortHelpers.FJFloat.Sorter
830 (null, a, new float[n], 0, n, 0,
831 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
832 MIN_ARRAY_SORT_GRAN : g).invoke();
833 }
834
835 /**
836 * Sorts the specified range of the array into ascending numerical order.
837 * The range to be sorted extends from the index {@code fromIndex},
838 * inclusive, to the index {@code toIndex}, exclusive. If
839 * {@code fromIndex == toIndex}, the range to be sorted is empty.
840 *
841 * <p>The {@code <} relation does not provide a total order on all float
842 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
843 * value compares neither less than, greater than, nor equal to any value,
844 * even itself. This method uses the total order imposed by the method
845 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
846 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
847 * other value and all {@code Float.NaN} values are considered equal.
848 *
849 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
850 * array into sub-arrays that are themselves sorted and then merged. When
851 * the sub-array length reaches a minimum granularity, the sub-array is
852 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort}
853 * method. If the length of the specified array is less than the minimum
854 * granularity, then it is sorted using the appropriate {@link
855 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a working
856 * space no greater than the size of the specified range of the original
857 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
858 * used to execute any parallel tasks.
859 *
860 * @param a the array to be sorted
861 * @param fromIndex the index of the first element, inclusive, to be sorted
862 * @param toIndex the index of the last element, exclusive, to be sorted
863 *
864 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
865 * @throws ArrayIndexOutOfBoundsException
866 * if {@code fromIndex < 0} or {@code toIndex > a.length}
867 *
868 * @since 1.8
869 */
870 public static void parallelSort(float[] a, int fromIndex, int toIndex) {
871 rangeCheck(a.length, fromIndex, toIndex);
872 int n = toIndex - fromIndex, p, g;
873 if (n <= MIN_ARRAY_SORT_GRAN ||
874 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
875 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
876 else
877 new ArraysParallelSortHelpers.FJFloat.Sorter
878 (null, a, new float[n], fromIndex, n, 0,
879 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
880 MIN_ARRAY_SORT_GRAN : g).invoke();
881 }
882
883 /**
884 * Sorts the specified array into ascending numerical order.
885 *
886 * <p>The {@code <} relation does not provide a total order on all double
887 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
888 * value compares neither less than, greater than, nor equal to any value,
889 * even itself. This method uses the total order imposed by the method
890 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
891 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
892 * other value and all {@code Double.NaN} values are considered equal.
893 *
894 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
895 * array into sub-arrays that are themselves sorted and then merged. When
896 * the sub-array length reaches a minimum granularity, the sub-array is
897 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort}
898 * method. If the length of the specified array is less than the minimum
899 * granularity, then it is sorted using the appropriate {@link
900 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a
901 * working space no greater than the size of the original array. The
902 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
903 * execute any parallel tasks.
904 *
905 * @param a the array to be sorted
906 *
907 * @since 1.8
908 */
909 public static void parallelSort(double[] a) {
910 int n = a.length, p, g;
911 if (n <= MIN_ARRAY_SORT_GRAN ||
912 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
913 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
914 else
915 new ArraysParallelSortHelpers.FJDouble.Sorter
916 (null, a, new double[n], 0, n, 0,
917 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
918 MIN_ARRAY_SORT_GRAN : g).invoke();
919 }
920
921 /**
922 * Sorts the specified range of the array into ascending numerical order.
923 * The range to be sorted extends from the index {@code fromIndex},
924 * inclusive, to the index {@code toIndex}, exclusive. If
925 * {@code fromIndex == toIndex}, the range to be sorted is empty.
926 *
927 * <p>The {@code <} relation does not provide a total order on all double
928 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
929 * value compares neither less than, greater than, nor equal to any value,
930 * even itself. This method uses the total order imposed by the method
931 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
932 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
933 * other value and all {@code Double.NaN} values are considered equal.
934 *
935 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
936 * array into sub-arrays that are themselves sorted and then merged. When
937 * the sub-array length reaches a minimum granularity, the sub-array is
938 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort}
939 * method. If the length of the specified array is less than the minimum
940 * granularity, then it is sorted using the appropriate {@link
941 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a working
942 * space no greater than the size of the specified range of the original
943 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is
944 * used to execute any parallel tasks.
945 *
946 * @param a the array to be sorted
947 * @param fromIndex the index of the first element, inclusive, to be sorted
948 * @param toIndex the index of the last element, exclusive, to be sorted
949 *
950 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
951 * @throws ArrayIndexOutOfBoundsException
952 * if {@code fromIndex < 0} or {@code toIndex > a.length}
953 *
954 * @since 1.8
955 */
956 public static void parallelSort(double[] a, int fromIndex, int toIndex) {
957 rangeCheck(a.length, fromIndex, toIndex);
958 int n = toIndex - fromIndex, p, g;
959 if (n <= MIN_ARRAY_SORT_GRAN ||
960 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
961 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
962 else
963 new ArraysParallelSortHelpers.FJDouble.Sorter
964 (null, a, new double[n], fromIndex, n, 0,
965 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
966 MIN_ARRAY_SORT_GRAN : g).invoke();
967 }
968
969 /**
970 * Sorts the specified array of objects into ascending order, according
971 * to the {@linkplain Comparable natural ordering} of its elements.
972 * All elements in the array must implement the {@link Comparable}
973 * interface. Furthermore, all elements in the array must be
974 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
975 * not throw a {@code ClassCastException} for any elements {@code e1}
976 * and {@code e2} in the array).
977 *
978 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
979 * not be reordered as a result of the sort.
980 *
981 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
982 * array into sub-arrays that are themselves sorted and then merged. When
983 * the sub-array length reaches a minimum granularity, the sub-array is
984 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
985 * method. If the length of the specified array is less than the minimum
986 * granularity, then it is sorted using the appropriate {@link
987 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
|
1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
46 import java.util.stream.Stream;
47 import java.util.stream.StreamSupport;
48
49 /**
50 * This class contains various methods for manipulating arrays (such as
51 * sorting and searching). This class also contains a static factory
52 * that allows arrays to be viewed as lists.
53 *
54 * <p>The methods in this class all throw a {@code NullPointerException},
55 * if the specified array reference is null, except where noted.
56 *
57 * <p>The documentation for the methods contained in this class includes
58 * brief descriptions of the <i>implementations</i>. Such descriptions should
59 * be regarded as <i>implementation notes</i>, rather than parts of the
60 * <i>specification</i>. Implementors should feel free to substitute other
61 * algorithms, so long as the specification itself is adhered to. (For
62 * example, the algorithm used by {@code sort(Object[])} does not have to be
63 * a MergeSort, but it does have to be <i>stable</i>.)
64 *
65 * <p>This class is a member of the
66 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
67 * Java Collections Framework</a>.
68 *
69 * @author Josh Bloch
70 * @author Neal Gafter
71 * @author John Rose
72 * @since 1.2
73 */
74 public class Arrays {
75
76 // Suppresses default constructor, ensuring non-instantiability.
77 private Arrays() {}
78
79 /**
80 * Checks that {@code fromIndex} and {@code toIndex} are in
81 * the range and throws an exception if they aren't.
82 */
83 static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
84 if (fromIndex > toIndex) {
85 throw new IllegalArgumentException(
86 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
87 }
88 if (fromIndex < 0) {
89 throw new ArrayIndexOutOfBoundsException(fromIndex);
90 }
91 if (toIndex > arrayLength) {
92 throw new ArrayIndexOutOfBoundsException(toIndex);
93 }
94 }
95
96 /**
97 * This flag allows system to run sorting in parallel.
98 */
99 private static final boolean RUN_IN_PARALLEL =
100 Runtime.getRuntime().availableProcessors() > 1;
101
102 /*
103 * Sorting methods. Note that all public "sort" methods take the
104 * same form: performing argument checks if necessary, and then
105 * expanding arguments into those required for the internal
106 * implementation methods residing in other package-private
107 * classes (except for legacyMergeSort, included in this class).
108 */
109
110 /**
111 * Sorts the specified array into ascending numerical order.
112 *
113 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
114 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
115 * offers O(n log(n)) performance on all data sets, and is typically
116 * faster than traditional (one-pivot) Quicksort implementations.
117 *
118 * @param a the array to be sorted
119 */
120 public static void sort(int[] a) {
121 DualPivotQuicksort.sort(a, false, 0, a.length);
122 }
123
124 /**
125 * Sorts the specified range of the array into ascending order. The range
126 * to be sorted extends from the index {@code fromIndex}, inclusive, to
127 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
128 * the range to be sorted is empty.
129 *
130 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
131 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
132 * offers O(n log(n)) performance on all data sets, and is typically
133 * faster than traditional (one-pivot) Quicksort implementations.
134 *
135 * @param a the array to be sorted
136 * @param fromIndex the index of the first element, inclusive, to be sorted
137 * @param toIndex the index of the last element, exclusive, to be sorted
138 *
139 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
140 * @throws ArrayIndexOutOfBoundsException
141 * if {@code fromIndex < 0} or {@code toIndex > a.length}
142 */
143 public static void sort(int[] a, int fromIndex, int toIndex) {
144 rangeCheck(a.length, fromIndex, toIndex);
145 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
146 }
147
148 /**
149 * Sorts the specified array into ascending numerical order.
150 *
151 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
152 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
153 * offers O(n log(n)) performance on all data sets, and is typically
154 * faster than traditional (one-pivot) Quicksort implementations.
155 *
156 * @param a the array to be sorted
157 */
158 public static void sort(long[] a) {
159 DualPivotQuicksort.sort(a, false, 0, a.length);
160 }
161
162 /**
163 * Sorts the specified range of the array into ascending order. The range
164 * to be sorted extends from the index {@code fromIndex}, inclusive, to
165 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
166 * the range to be sorted is empty.
167 *
168 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
169 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
170 * offers O(n log(n)) performance on all data sets, and is typically
171 * faster than traditional (one-pivot) Quicksort implementations.
172 *
173 * @param a the array to be sorted
174 * @param fromIndex the index of the first element, inclusive, to be sorted
175 * @param toIndex the index of the last element, exclusive, to be sorted
176 *
177 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
178 * @throws ArrayIndexOutOfBoundsException
179 * if {@code fromIndex < 0} or {@code toIndex > a.length}
180 */
181 public static void sort(long[] a, int fromIndex, int toIndex) {
182 rangeCheck(a.length, fromIndex, toIndex);
183 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
184 }
185
186 /**
187 * Sorts the specified array into ascending numerical order.
188 *
189 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
190 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
191 * offers O(n log(n)) performance on all data sets, and is typically
192 * faster than traditional (one-pivot) Quicksort implementations.
193 *
194 * @param a the array to be sorted
195 */
196 public static void sort(byte[] a) {
197 DualPivotQuicksort.sort(a, false, 0, a.length);
198 }
199
200 /**
201 * Sorts the specified range of the array into ascending order. The range
202 * to be sorted extends from the index {@code fromIndex}, inclusive, to
203 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
204 * the range to be sorted is empty.
205 *
206 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
207 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
208 * offers O(n log(n)) performance on all data sets, and is typically
209 * faster than traditional (one-pivot) Quicksort implementations.
210 *
211 * @param a the array to be sorted
212 * @param fromIndex the index of the first element, inclusive, to be sorted
213 * @param toIndex the index of the last element, exclusive, to be sorted
214 *
215 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
216 * @throws ArrayIndexOutOfBoundsException
217 * if {@code fromIndex < 0} or {@code toIndex > a.length}
218 */
219 public static void sort(byte[] a, int fromIndex, int toIndex) {
220 rangeCheck(a.length, fromIndex, toIndex);
221 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
222 }
223
224 /**
225 * Sorts the specified array into ascending numerical order.
226 *
227 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
228 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
229 * offers O(n log(n)) performance on all data sets, and is typically
230 * faster than traditional (one-pivot) Quicksort implementations.
231 *
232 * @param a the array to be sorted
233 */
234 public static void sort(char[] a) {
235 DualPivotQuicksort.sort(a, false, 0, a.length);
236 }
237
238 /**
239 * Sorts the specified range of the array into ascending order. The range
240 * to be sorted extends from the index {@code fromIndex}, inclusive, to
241 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
242 * the range to be sorted is empty.
243 *
244 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
245 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
246 * offers O(n log(n)) performance on all data sets, and is typically
247 * faster than traditional (one-pivot) Quicksort implementations.
248 *
249 * @param a the array to be sorted
250 * @param fromIndex the index of the first element, inclusive, to be sorted
251 * @param toIndex the index of the last element, exclusive, to be sorted
252 *
253 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
254 * @throws ArrayIndexOutOfBoundsException
255 * if {@code fromIndex < 0} or {@code toIndex > a.length}
256 */
257 public static void sort(char[] a, int fromIndex, int toIndex) {
258 rangeCheck(a.length, fromIndex, toIndex);
259 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
260 }
261
262 /**
263 * Sorts the specified array into ascending numerical order.
264 *
265 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
266 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
267 * offers O(n log(n)) performance on all data sets, and is typically
268 * faster than traditional (one-pivot) Quicksort implementations.
269 *
270 * @param a the array to be sorted
271 */
272 public static void sort(short[] a) {
273 DualPivotQuicksort.sort(a, false, 0, a.length);
274 }
275
276 /**
277 * Sorts the specified range of the array into ascending order. The range
278 * to be sorted extends from the index {@code fromIndex}, inclusive, to
279 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
280 * the range to be sorted is empty.
281 *
282 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
283 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
284 * offers O(n log(n)) performance on all data sets, and is typically
285 * faster than traditional (one-pivot) Quicksort implementations.
286 *
287 * @param a the array to be sorted
288 * @param fromIndex the index of the first element, inclusive, to be sorted
289 * @param toIndex the index of the last element, exclusive, to be sorted
290 *
291 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
292 * @throws ArrayIndexOutOfBoundsException
293 * if {@code fromIndex < 0} or {@code toIndex > a.length}
294 */
295 public static void sort(short[] a, int fromIndex, int toIndex) {
296 rangeCheck(a.length, fromIndex, toIndex);
297 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
298 }
299
300 /**
301 * Sorts the specified array into ascending numerical order.
302 *
303 * <p>The {@code <} relation does not provide a total order on all float
304 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
305 * value compares neither less than, greater than, nor equal to any value,
306 * even itself. This method uses the total order imposed by the method
307 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
308 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
309 * other value and all {@code Float.NaN} values are considered equal.
310 *
311 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
312 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
313 * offers O(n log(n)) performance on all data sets, and is typically
314 * faster than traditional (one-pivot) Quicksort implementations.
315 *
316 * @param a the array to be sorted
317 */
318 public static void sort(float[] a) {
319 DualPivotQuicksort.sort(a, false, 0, a.length);
320 }
321
322 /**
323 * Sorts the specified range of the array into ascending order. The range
324 * to be sorted extends from the index {@code fromIndex}, inclusive, to
325 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
326 * the range to be sorted is empty.
327 *
328 * <p>The {@code <} relation does not provide a total order on all float
329 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
330 * value compares neither less than, greater than, nor equal to any value,
331 * even itself. This method uses the total order imposed by the method
332 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
333 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
334 * other value and all {@code Float.NaN} values are considered equal.
335 *
336 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
337 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
338 * offers O(n log(n)) performance on all data sets, and is typically
339 * faster than traditional (one-pivot) Quicksort implementations.
340 *
341 * @param a the array to be sorted
342 * @param fromIndex the index of the first element, inclusive, to be sorted
343 * @param toIndex the index of the last element, exclusive, to be sorted
344 *
345 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
346 * @throws ArrayIndexOutOfBoundsException
347 * if {@code fromIndex < 0} or {@code toIndex > a.length}
348 */
349 public static void sort(float[] a, int fromIndex, int toIndex) {
350 rangeCheck(a.length, fromIndex, toIndex);
351 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
352 }
353
354 /**
355 * Sorts the specified array into ascending numerical order.
356 *
357 * <p>The {@code <} relation does not provide a total order on all double
358 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
359 * value compares neither less than, greater than, nor equal to any value,
360 * even itself. This method uses the total order imposed by the method
361 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
362 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
363 * other value and all {@code Double.NaN} values are considered equal.
364 *
365 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
366 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
367 * offers O(n log(n)) performance on all data sets, and is typically
368 * faster than traditional (one-pivot) Quicksort implementations.
369 *
370 * @param a the array to be sorted
371 */
372 public static void sort(double[] a) {
373 DualPivotQuicksort.sort(a, false, 0, a.length);
374 }
375
376 /**
377 * Sorts the specified range of the array into ascending order. The range
378 * to be sorted extends from the index {@code fromIndex}, inclusive, to
379 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
380 * the range to be sorted is empty.
381 *
382 * <p>The {@code <} relation does not provide a total order on all double
383 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
384 * value compares neither less than, greater than, nor equal to any value,
385 * even itself. This method uses the total order imposed by the method
386 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
387 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
388 * other value and all {@code Double.NaN} values are considered equal.
389 *
390 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
391 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
392 * offers O(n log(n)) performance on all data sets, and is typically
393 * faster than traditional (one-pivot) Quicksort implementations.
394 *
395 * @param a the array to be sorted
396 * @param fromIndex the index of the first element, inclusive, to be sorted
397 * @param toIndex the index of the last element, exclusive, to be sorted
398 *
399 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
400 * @throws ArrayIndexOutOfBoundsException
401 * if {@code fromIndex < 0} or {@code toIndex > a.length}
402 */
403 public static void sort(double[] a, int fromIndex, int toIndex) {
404 rangeCheck(a.length, fromIndex, toIndex);
405 DualPivotQuicksort.sort(a, false, fromIndex, toIndex);
406 }
407
408 /**
409 * Sorts the specified array into ascending numerical order.
410 *
411 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
412 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
413 * offers O(n log(n)) performance on all data sets, and is typically
414 * faster than traditional (one-pivot) Quicksort implementations.
415 *
416 * @param a the array to be sorted
417 *
418 * @since 1.8
419 */
420 public static void parallelSort(int[] a) {
421 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
422 }
423
424 /**
425 * Sorts the specified range of the array into ascending numerical order.
426 * The range to be sorted extends from the index {@code fromIndex},
427 * inclusive, to the index {@code toIndex}, exclusive. If
428 * {@code fromIndex == toIndex}, the range to be sorted is empty.
429 *
430 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
431 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
432 * offers O(n log(n)) performance on all data sets, and is typically
433 * faster than traditional (one-pivot) Quicksort implementations.
434 *
435 * @param a the array to be sorted
436 * @param fromIndex the index of the first element, inclusive, to be sorted
437 * @param toIndex the index of the last element, exclusive, to be sorted
438 *
439 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
440 * @throws ArrayIndexOutOfBoundsException
441 * if {@code fromIndex < 0} or {@code toIndex > a.length}
442 *
443 * @since 1.8
444 */
445 public static void parallelSort(int[] a, int fromIndex, int toIndex) {
446 rangeCheck(a.length, fromIndex, toIndex);
447 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
448 }
449
450 /**
451 * Sorts the specified array into ascending numerical order.
452 *
453 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
454 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
455 * offers O(n log(n)) performance on all data sets, and is typically
456 * faster than traditional (one-pivot) Quicksort implementations.
457 *
458 * @param a the array to be sorted
459 *
460 * @since 1.8
461 */
462 public static void parallelSort(long[] a) {
463 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
464 }
465
466 /**
467 * Sorts the specified range of the array into ascending numerical order.
468 * The range to be sorted extends from the index {@code fromIndex},
469 * inclusive, to the index {@code toIndex}, exclusive. If
470 * {@code fromIndex == toIndex}, the range to be sorted is empty.
471 *
472 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
473 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
474 * offers O(n log(n)) performance on all data sets, and is typically
475 * faster than traditional (one-pivot) Quicksort implementations.
476 *
477 * @param a the array to be sorted
478 * @param fromIndex the index of the first element, inclusive, to be sorted
479 * @param toIndex the index of the last element, exclusive, to be sorted
480 *
481 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
482 * @throws ArrayIndexOutOfBoundsException
483 * if {@code fromIndex < 0} or {@code toIndex > a.length}
484 *
485 * @since 1.8
486 */
487 public static void parallelSort(long[] a, int fromIndex, int toIndex) {
488 rangeCheck(a.length, fromIndex, toIndex);
489 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
490 }
491
492 /**
493 * Sorts the specified array into ascending numerical order.
494 *
495 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
496 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
497 * offers O(n log(n)) performance on all data sets, and is typically
498 * faster than traditional (one-pivot) Quicksort implementations.
499 *
500 * @param a the array to be sorted
501 *
502 * @since 1.8
503 */
504 public static void parallelSort(byte[] a) {
505 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
506 }
507
508 /**
509 * Sorts the specified range of the array into ascending numerical order.
510 * The range to be sorted extends from the index {@code fromIndex},
511 * inclusive, to the index {@code toIndex}, exclusive. If
512 * {@code fromIndex == toIndex}, the range to be sorted is empty.
513 *
514 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
515 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
516 * offers O(n log(n)) performance on all data sets, and is typically
517 * faster than traditional (one-pivot) Quicksort implementations.
518 *
519 * @param a the array to be sorted
520 * @param fromIndex the index of the first element, inclusive, to be sorted
521 * @param toIndex the index of the last element, exclusive, to be sorted
522 *
523 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
524 * @throws ArrayIndexOutOfBoundsException
525 * if {@code fromIndex < 0} or {@code toIndex > a.length}
526 *
527 * @since 1.8
528 */
529 public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
530 rangeCheck(a.length, fromIndex, toIndex);
531 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
532 }
533
534 /**
535 * Sorts the specified array into ascending numerical order.
536 *
537 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
538 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
539 * offers O(n log(n)) performance on all data sets, and is typically
540 * faster than traditional (one-pivot) Quicksort implementations.
541 *
542 * @param a the array to be sorted
543 *
544 * @since 1.8
545 */
546 public static void parallelSort(char[] a) {
547 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
548 }
549
550 /**
551 * Sorts the specified range of the array into ascending numerical order.
552 * The range to be sorted extends from the index {@code fromIndex},
553 * inclusive, to the index {@code toIndex}, exclusive. If
554 * {@code fromIndex == toIndex}, the range to be sorted is empty.
555 *
556 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
557 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
558 * offers O(n log(n)) performance on all data sets, and is typically
559 * faster than traditional (one-pivot) Quicksort implementations.
560 *
561 * @param a the array to be sorted
562 * @param fromIndex the index of the first element, inclusive, to be sorted
563 * @param toIndex the index of the last element, exclusive, to be sorted
564 *
565 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
566 * @throws ArrayIndexOutOfBoundsException
567 * if {@code fromIndex < 0} or {@code toIndex > a.length}
568 *
569 * @since 1.8
570 */
571 public static void parallelSort(char[] a, int fromIndex, int toIndex) {
572 rangeCheck(a.length, fromIndex, toIndex);
573 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
574 }
575
576 /**
577 * Sorts the specified array into ascending numerical order.
578 *
579 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
580 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
581 * offers O(n log(n)) performance on all data sets, and is typically
582 * faster than traditional (one-pivot) Quicksort implementations.
583 *
584 * @param a the array to be sorted
585 *
586 * @since 1.8
587 */
588 public static void parallelSort(short[] a) {
589 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
590 }
591
592 /**
593 * Sorts the specified range of the array into ascending numerical order.
594 * The range to be sorted extends from the index {@code fromIndex},
595 * inclusive, to the index {@code toIndex}, exclusive. If
596 * {@code fromIndex == toIndex}, the range to be sorted is empty.
597 *
598 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
599 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
600 * offers O(n log(n)) performance on all data sets, and is typically
601 * faster than traditional (one-pivot) Quicksort implementations.
602 *
603 * @param a the array to be sorted
604 * @param fromIndex the index of the first element, inclusive, to be sorted
605 * @param toIndex the index of the last element, exclusive, to be sorted
606 *
607 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
608 * @throws ArrayIndexOutOfBoundsException
609 * if {@code fromIndex < 0} or {@code toIndex > a.length}
610 *
611 * @since 1.8
612 */
613 public static void parallelSort(short[] a, int fromIndex, int toIndex) {
614 rangeCheck(a.length, fromIndex, toIndex);
615 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
616 }
617
618 /**
619 * Sorts the specified array into ascending numerical order.
620 *
621 * <p>The {@code <} relation does not provide a total order on all float
622 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
623 * value compares neither less than, greater than, nor equal to any value,
624 * even itself. This method uses the total order imposed by the method
625 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
626 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
627 * other value and all {@code Float.NaN} values are considered equal.
628 *
629 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
630 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
631 * offers O(n log(n)) performance on all data sets, and is typically
632 * faster than traditional (one-pivot) Quicksort implementations.
633 *
634 * @param a the array to be sorted
635 *
636 * @since 1.8
637 */
638 public static void parallelSort(float[] a) {
639 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
640 }
641
642 /**
643 * Sorts the specified range of the array into ascending numerical order.
644 * The range to be sorted extends from the index {@code fromIndex},
645 * inclusive, to the index {@code toIndex}, exclusive. If
646 * {@code fromIndex == toIndex}, the range to be sorted is empty.
647 *
648 * <p>The {@code <} relation does not provide a total order on all float
649 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
650 * value compares neither less than, greater than, nor equal to any value,
651 * even itself. This method uses the total order imposed by the method
652 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
653 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
654 * other value and all {@code Float.NaN} values are considered equal.
655 *
656 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
657 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
658 * offers O(n log(n)) performance on all data sets, and is typically
659 * faster than traditional (one-pivot) Quicksort implementations.
660 *
661 * @param a the array to be sorted
662 * @param fromIndex the index of the first element, inclusive, to be sorted
663 * @param toIndex the index of the last element, exclusive, to be sorted
664 *
665 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
666 * @throws ArrayIndexOutOfBoundsException
667 * if {@code fromIndex < 0} or {@code toIndex > a.length}
668 *
669 * @since 1.8
670 */
671 public static void parallelSort(float[] a, int fromIndex, int toIndex) {
672 rangeCheck(a.length, fromIndex, toIndex);
673 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
674 }
675
676 /**
677 * Sorts the specified array into ascending numerical order.
678 *
679 * <p>The {@code <} relation does not provide a total order on all double
680 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
681 * value compares neither less than, greater than, nor equal to any value,
682 * even itself. This method uses the total order imposed by the method
683 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
684 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
685 * other value and all {@code Double.NaN} values are considered equal.
686 *
687 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
688 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
689 * offers O(n log(n)) performance on all data sets, and is typically
690 * faster than traditional (one-pivot) Quicksort implementations.
691 *
692 * @param a the array to be sorted
693 *
694 * @since 1.8
695 */
696 public static void parallelSort(double[] a) {
697 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, 0, a.length);
698 }
699
700 /**
701 * Sorts the specified range of the array into ascending numerical order.
702 * The range to be sorted extends from the index {@code fromIndex},
703 * inclusive, to the index {@code toIndex}, exclusive. If
704 * {@code fromIndex == toIndex}, the range to be sorted is empty.
705 *
706 * <p>The {@code <} relation does not provide a total order on all double
707 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
708 * value compares neither less than, greater than, nor equal to any value,
709 * even itself. This method uses the total order imposed by the method
710 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
711 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
712 * other value and all {@code Double.NaN} values are considered equal.
713 *
714 * @implNote The sorting algorithm is a Dual-Pivot Quicksort by
715 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
716 * offers O(n log(n)) performance on all data sets, and is typically
717 * faster than traditional (one-pivot) Quicksort implementations.
718 *
719 * @param a the array to be sorted
720 * @param fromIndex the index of the first element, inclusive, to be sorted
721 * @param toIndex the index of the last element, exclusive, to be sorted
722 *
723 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
724 * @throws ArrayIndexOutOfBoundsException
725 * if {@code fromIndex < 0} or {@code toIndex > a.length}
726 *
727 * @since 1.8
728 */
729 public static void parallelSort(double[] a, int fromIndex, int toIndex) {
730 rangeCheck(a.length, fromIndex, toIndex);
731 DualPivotQuicksort.sort(a, RUN_IN_PARALLEL, fromIndex, toIndex);
732 }
733
734 /**
735 * A comparator that implements the natural ordering of a group of
736 * mutually comparable elements. May be used when a supplied
737 * comparator is null. To simplify code-sharing within underlying
738 * implementations, the compare method only declares type Object
739 * for its second argument.
740 *
741 * Arrays class implementor's note: It is an empirical matter
742 * whether ComparableTimSort offers any performance benefit over
743 * TimSort used with this comparator. If not, you are better off
744 * deleting or bypassing ComparableTimSort. There is currently no
745 * empirical case for separating them for parallel sorting, so all
746 * public Object parallelSort methods use the same comparator
747 * based implementation.
748 */
749 static final class NaturalOrder implements Comparator<Object> {
750 @SuppressWarnings("unchecked")
751 public int compare(Object first, Object second) {
752 return ((Comparable<Object>)first).compareTo(second);
753 }
754 static final NaturalOrder INSTANCE = new NaturalOrder();
755 }
756
757 /**
758 * The minimum array length below which a parallel sorting
759 * algorithm will not further partition the sorting task. Using
760 * smaller sizes typically results in memory contention across
761 * tasks that makes parallel speedups unlikely.
762 */
763 private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
764
765 /**
766 * Sorts the specified array of objects into ascending order, according
767 * to the {@linkplain Comparable natural ordering} of its elements.
768 * All elements in the array must implement the {@link Comparable}
769 * interface. Furthermore, all elements in the array must be
770 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
771 * not throw a {@code ClassCastException} for any elements {@code e1}
772 * and {@code e2} in the array).
773 *
774 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
775 * not be reordered as a result of the sort.
776 *
777 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
778 * array into sub-arrays that are themselves sorted and then merged. When
779 * the sub-array length reaches a minimum granularity, the sub-array is
780 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort}
781 * method. If the length of the specified array is less than the minimum
782 * granularity, then it is sorted using the appropriate {@link
783 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a
|