1 /*
2 * Copyright 2009 Sun Microsystems, Inc. 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. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package java.util;
27
28 /**
29 * This class implements the Dual-Pivot Quicksort algorithm by
30 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
31 * offers O(n log(n)) performance on many data sets that cause other
32 * quicksorts to degrade to quadratic performance, and is typically
33 * faster than traditional (one-pivot) Quicksort implementations.
34 *
35 * @author Vladimir Yaroslavskiy
36 * @author Jon Bentley
37 * @author Josh Bloch
38 *
39 * @version 2009.11.29 m765.827.12i
40 */
41 final class DualPivotQuicksort {
42
43 /**
44 * Prevents instantiation.
45 */
46 private DualPivotQuicksort() {}
47
48 /*
49 * Tuning parameters.
50 */
51
52 /**
53 * If the length of an array to be sorted is less than this
54 * constant, insertion sort is used in preference to Quicksort.
55 */
56 private static final int INSERTION_SORT_THRESHOLD = 32;
57
58 /**
59 * If the length of a byte array to be sorted is greater than
60 * this constant, counting sort is used in preference to Quicksort.
61 */
62 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
63
64 /**
65 * If the length of a short or char array to be sorted is greater
66 * than this constant, counting sort is used in preference to Quicksort.
67 */
68 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
69
70 /*
71 * Sorting methods for 7 primitive types.
72 */
73
74 /**
75 * Sorts the specified array into ascending numerical order.
76 *
77 * @param a the array to be sorted
78 */
79 public static void sort(int[] a) {
80 doSort(a, 0, a.length - 1);
81 }
82
83 /**
84 * Sorts the specified range of the array into ascending order. The range
85 * to be sorted extends from the index {@code fromIndex}, inclusive, to
86 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
87 * the range to be sorted is empty (and the call is a no-op).
88 *
89 * @param a the array to be sorted
90 * @param fromIndex the index of the first element, inclusive, to be sorted
91 * @param toIndex the index of the last element, exclusive, to be sorted
92 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
93 * @throws ArrayIndexOutOfBoundsException
94 * if {@code fromIndex < 0} or {@code toIndex > a.length}
95 */
96 public static void sort(int[] a, int fromIndex, int toIndex) {
97 rangeCheck(a.length, fromIndex, toIndex);
98 doSort(a, fromIndex, toIndex - 1);
99 }
100
101 /**
102 * Sorts the specified range of the array into ascending order. This
103 * method differs from the public {@code sort} method in that the
104 * {@code right} index is inclusive, and it does no range checking
105 * on {@code left} or {@code right}.
106 *
107 * @param a the array to be sorted
108 * @param left the index of the first element, inclusive, to be sorted
109 * @param right the index of the last element, inclusive, to be sorted
110 */
111 private static void doSort(int[] a, int left, int right) {
112 // Use insertion sort on tiny arrays
113 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
114 for (int i = left + 1; i <= right; i++) {
115 int ai = a[i];
116 int j;
117 for (j = i - 1; j >= left && ai < a[j]; j--) {
118 a[j + 1] = a[j];
119 }
120 a[j + 1] = ai;
121 }
122 } else { // Use Dual-Pivot Quicksort on large arrays
123 dualPivotQuicksort(a, left, right);
124 }
125 }
126
127 /**
128 * Sorts the specified range of the array into ascending order by the
129 * Dual-Pivot Quicksort algorithm.
130 *
131 * @param a the array to be sorted
132 * @param left the index of the first element, inclusive, to be sorted
133 * @param right the index of the last element, inclusive, to be sorted
134 */
135 private static void dualPivotQuicksort(int[] a, int left, int right) {
136 // Compute indices of five evenly spaced elements
137 int sixth = (right - left + 1) / 6;
138 int e1 = left + sixth;
139 int e5 = right - sixth;
140 int e3 = (left + right) >>> 1; // The midpoint
141 int e4 = e3 + sixth;
142 int e2 = e3 - sixth;
143
144 // Sort these elements using a 5-element sorting network
145 int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
146
147 if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
148 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
149 if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
150 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
151 if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
152 if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
153 if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
154 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
155 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
156
157 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
158
159 /*
160 * Use the second and fourth of the five sorted elements as pivots.
161 * These values are inexpensive approximations of the first and
162 * second terciles of the array. Note that pivot1 <= pivot2.
163 *
164 * The pivots are stored in local variables, and the first and
165 * the last of the elements to be sorted are moved to the locations
166 * formerly occupied by the pivots. When partitioning is complete,
167 * the pivots are swapped back into their final positions, and
168 * excluded from subsequent sorting.
169 */
170 int pivot1 = ae2; a[e2] = a[left];
171 int pivot2 = ae4; a[e4] = a[right];
172
173 // Pointers
174 int less = left + 1; // The index of first element of center part
175 int great = right - 1; // The index before first element of right part
176
177 boolean pivotsDiffer = (pivot1 != pivot2);
178
179 if (pivotsDiffer) {
180 /*
181 * Partitioning:
182 *
183 * left part center part right part
184 * +------------------------------------------------------------+
185 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
186 * +------------------------------------------------------------+
187 * ^ ^ ^
188 * | | |
189 * less k great
190 *
191 * Invariants:
192 *
193 * all in (left, less) < pivot1
194 * pivot1 <= all in [less, k) <= pivot2
195 * all in (great, right) > pivot2
196 *
197 * Pointer k is the first index of ?-part
198 */
199 outer:
200 for (int k = less; k <= great; k++) {
201 int ak = a[k];
202 if (ak < pivot1) { // Move a[k] to left part
203 if (k != less) {
204 a[k] = a[less];
205 a[less] = ak;
206 }
207 less++;
208 } else if (ak > pivot2) { // Move a[k] to right part
209 while (a[great] > pivot2) {
210 if (great-- == k) {
211 break outer;
212 }
213 }
214 if (a[great] < pivot1) {
215 a[k] = a[less];
216 a[less++] = a[great];
217 a[great--] = ak;
218 } else { // pivot1 <= a[great] <= pivot2
219 a[k] = a[great];
220 a[great--] = ak;
221 }
222 }
223 }
224 } else { // Pivots are equal
225 /*
226 * Partition degenerates to the traditional 3-way,
227 * or "Dutch National Flag", partition:
228 *
229 * left part center part right part
230 * +----------------------------------------------+
231 * | < pivot | == pivot | ? | > pivot |
232 * +----------------------------------------------+
233 * ^ ^ ^
234 * | | |
235 * less k great
236 *
237 * Invariants:
238 *
239 * all in (left, less) < pivot
240 * all in [less, k) == pivot
241 * all in (great, right) > pivot
242 *
243 * Pointer k is the first index of ?-part
244 */
245 for (int k = less; k <= great; k++) {
246 int ak = a[k];
247 if (ak == pivot1) {
248 continue;
249 }
250 if (ak < pivot1) { // Move a[k] to left part
251 if (k != less) {
252 a[k] = a[less];
253 a[less] = ak;
254 }
255 less++;
256 } else { // (a[k] > pivot1) - Move a[k] to right part
257 /*
258 * We know that pivot1 == a[e3] == pivot2. Thus, we know
259 * that great will still be >= k when the following loop
260 * terminates, even though we don't test for it explicitly.
261 * In other words, a[e3] acts as a sentinel for great.
262 */
263 while (a[great] > pivot1) {
264 great--;
265 }
266 if (a[great] < pivot1) {
267 a[k] = a[less];
268 a[less++] = a[great];
269 a[great--] = ak;
270 } else { // a[great] == pivot1
271 a[k] = pivot1;
272 a[great--] = ak;
273 }
274 }
275 }
276 }
277
278 // Swap pivots into their final positions
279 a[left] = a[less - 1]; a[less - 1] = pivot1;
280 a[right] = a[great + 1]; a[great + 1] = pivot2;
281
282 // Sort left and right parts recursively, excluding known pivot values
283 doSort(a, left, less - 2);
284 doSort(a, great + 2, right);
285
286 /*
287 * If pivot1 == pivot2, all elements from center
288 * part are equal and, therefore, already sorted
289 */
290 if (!pivotsDiffer) {
291 return;
292 }
293
294 /*
295 * If center part is too large (comprises > 2/3 of the array),
296 * swap internal pivot values to ends
297 */
298 if (less < e1 && great > e5) {
299 while (a[less] == pivot1) {
300 less++;
301 }
302 while (a[great] == pivot2) {
303 great--;
304 }
305
306 /*
307 * Partitioning:
308 *
309 * left part center part right part
310 * +----------------------------------------------------------+
311 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
312 * +----------------------------------------------------------+
313 * ^ ^ ^
314 * | | |
315 * less k great
316 *
317 * Invariants:
318 *
319 * all in (*, less) == pivot1
320 * pivot1 < all in [less, k) < pivot2
321 * all in (great, *) == pivot2
322 *
323 * Pointer k is the first index of ?-part
324 */
325 outer:
326 for (int k = less; k <= great; k++) {
327 int ak = a[k];
328 if (ak == pivot2) { // Move a[k] to right part
329 while (a[great] == pivot2) {
330 if (great-- == k) {
331 break outer;
332 }
333 }
334 if (a[great] == pivot1) {
335 a[k] = a[less];
336 a[less++] = pivot1;
337 } else { // pivot1 < a[great] < pivot2
338 a[k] = a[great];
339 }
340 a[great--] = pivot2;
341 } else if (ak == pivot1) { // Move a[k] to left part
342 a[k] = a[less];
343 a[less++] = pivot1;
344 }
345 }
346 }
347
348 // Sort center part recursively, excluding known pivot values
349 doSort(a, less, great);
350 }
351
352 /**
353 * Sorts the specified array into ascending numerical order.
354 *
355 * @param a the array to be sorted
356 */
357 public static void sort(long[] a) {
358 doSort(a, 0, a.length - 1);
359 }
360
361 /**
362 * Sorts the specified range of the array into ascending order. The range
363 * to be sorted extends from the index {@code fromIndex}, inclusive, to
364 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
365 * the range to be sorted is empty (and the call is a no-op).
366 *
367 * @param a the array to be sorted
368 * @param fromIndex the index of the first element, inclusive, to be sorted
369 * @param toIndex the index of the last element, exclusive, to be sorted
370 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
371 * @throws ArrayIndexOutOfBoundsException
372 * if {@code fromIndex < 0} or {@code toIndex > a.length}
373 */
374 public static void sort(long[] a, int fromIndex, int toIndex) {
375 rangeCheck(a.length, fromIndex, toIndex);
376 doSort(a, fromIndex, toIndex - 1);
377 }
378
379 /**
380 * Sorts the specified range of the array into ascending order. This
381 * method differs from the public {@code sort} method in that the
382 * {@code right} index is inclusive, and it does no range checking on
383 * {@code left} or {@code right}.
384 *
385 * @param a the array to be sorted
386 * @param left the index of the first element, inclusive, to be sorted
387 * @param right the index of the last element, inclusive, to be sorted
388 */
389 private static void doSort(long[] a, int left, int right) {
390 // Use insertion sort on tiny arrays
391 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
392 for (int i = left + 1; i <= right; i++) {
393 long ai = a[i];
394 int j;
395 for (j = i - 1; j >= left && ai < a[j]; j--) {
396 a[j + 1] = a[j];
397 }
398 a[j + 1] = ai;
399 }
400 } else { // Use Dual-Pivot Quicksort on large arrays
401 dualPivotQuicksort(a, left, right);
402 }
403 }
404
405 /**
406 * Sorts the specified range of the array into ascending order by the
407 * Dual-Pivot Quicksort algorithm.
408 *
409 * @param a the array to be sorted
410 * @param left the index of the first element, inclusive, to be sorted
411 * @param right the index of the last element, inclusive, to be sorted
412 */
413 private static void dualPivotQuicksort(long[] a, int left, int right) {
414 // Compute indices of five evenly spaced elements
415 int sixth = (right - left + 1) / 6;
416 int e1 = left + sixth;
417 int e5 = right - sixth;
418 int e3 = (left + right) >>> 1; // The midpoint
419 int e4 = e3 + sixth;
420 int e2 = e3 - sixth;
421
422 // Sort these elements using a 5-element sorting network
423 long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
424
425 if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
426 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
427 if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
428 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
429 if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
430 if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
431 if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
432 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
433 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
434
435 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
436
437 /*
438 * Use the second and fourth of the five sorted elements as pivots.
439 * These values are inexpensive approximations of the first and
440 * second terciles of the array. Note that pivot1 <= pivot2.
441 *
442 * The pivots are stored in local variables, and the first and
443 * the last of the elements to be sorted are moved to the locations
444 * formerly occupied by the pivots. When partitioning is complete,
445 * the pivots are swapped back into their final positions, and
446 * excluded from subsequent sorting.
447 */
448 long pivot1 = ae2; a[e2] = a[left];
449 long pivot2 = ae4; a[e4] = a[right];
450
451 // Pointers
452 int less = left + 1; // The index of first element of center part
453 int great = right - 1; // The index before first element of right part
454
455 boolean pivotsDiffer = (pivot1 != pivot2);
456
457 if (pivotsDiffer) {
458 /*
459 * Partitioning:
460 *
461 * left part center part right part
462 * +------------------------------------------------------------+
463 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
464 * +------------------------------------------------------------+
465 * ^ ^ ^
466 * | | |
467 * less k great
468 *
469 * Invariants:
470 *
471 * all in (left, less) < pivot1
472 * pivot1 <= all in [less, k) <= pivot2
473 * all in (great, right) > pivot2
474 *
475 * Pointer k is the first index of ?-part
476 */
477 outer:
478 for (int k = less; k <= great; k++) {
479 long ak = a[k];
480 if (ak < pivot1) { // Move a[k] to left part
481 if (k != less) {
482 a[k] = a[less];
483 a[less] = ak;
484 }
485 less++;
486 } else if (ak > pivot2) { // Move a[k] to right part
487 while (a[great] > pivot2) {
488 if (great-- == k) {
489 break outer;
490 }
491 }
492 if (a[great] < pivot1) {
493 a[k] = a[less];
494 a[less++] = a[great];
495 a[great--] = ak;
496 } else { // pivot1 <= a[great] <= pivot2
497 a[k] = a[great];
498 a[great--] = ak;
499 }
500 }
501 }
502 } else { // Pivots are equal
503 /*
504 * Partition degenerates to the traditional 3-way,
505 * or "Dutch National Flag", partition:
506 *
507 * left part center part right part
508 * +----------------------------------------------+
509 * | < pivot | == pivot | ? | > pivot |
510 * +----------------------------------------------+
511 * ^ ^ ^
512 * | | |
513 * less k great
514 *
515 * Invariants:
516 *
517 * all in (left, less) < pivot
518 * all in [less, k) == pivot
519 * all in (great, right) > pivot
520 *
521 * Pointer k is the first index of ?-part
522 */
523 for (int k = less; k <= great; k++) {
524 long ak = a[k];
525 if (ak == pivot1) {
526 continue;
527 }
528 if (ak < pivot1) { // Move a[k] to left part
529 if (k != less) {
530 a[k] = a[less];
531 a[less] = ak;
532 }
533 less++;
534 } else { // (a[k] > pivot1) - Move a[k] to right part
535 /*
536 * We know that pivot1 == a[e3] == pivot2. Thus, we know
537 * that great will still be >= k when the following loop
538 * terminates, even though we don't test for it explicitly.
539 * In other words, a[e3] acts as a sentinel for great.
540 */
541 while (a[great] > pivot1) {
542 great--;
543 }
544 if (a[great] < pivot1) {
545 a[k] = a[less];
546 a[less++] = a[great];
547 a[great--] = ak;
548 } else { // a[great] == pivot1
549 a[k] = pivot1;
550 a[great--] = ak;
551 }
552 }
553 }
554 }
555
556 // Swap pivots into their final positions
557 a[left] = a[less - 1]; a[less - 1] = pivot1;
558 a[right] = a[great + 1]; a[great + 1] = pivot2;
559
560 // Sort left and right parts recursively, excluding known pivot values
561 doSort(a, left, less - 2);
562 doSort(a, great + 2, right);
563
564 /*
565 * If pivot1 == pivot2, all elements from center
566 * part are equal and, therefore, already sorted
567 */
568 if (!pivotsDiffer) {
569 return;
570 }
571
572 /*
573 * If center part is too large (comprises > 2/3 of the array),
574 * swap internal pivot values to ends
575 */
576 if (less < e1 && great > e5) {
577 while (a[less] == pivot1) {
578 less++;
579 }
580 while (a[great] == pivot2) {
581 great--;
582 }
583
584 /*
585 * Partitioning:
586 *
587 * left part center part right part
588 * +----------------------------------------------------------+
589 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
590 * +----------------------------------------------------------+
591 * ^ ^ ^
592 * | | |
593 * less k great
594 *
595 * Invariants:
596 *
597 * all in (*, less) == pivot1
598 * pivot1 < all in [less, k) < pivot2
599 * all in (great, *) == pivot2
600 *
601 * Pointer k is the first index of ?-part
602 */
603 outer:
604 for (int k = less; k <= great; k++) {
605 long ak = a[k];
606 if (ak == pivot2) { // Move a[k] to right part
607 while (a[great] == pivot2) {
608 if (great-- == k) {
609 break outer;
610 }
611 }
612 if (a[great] == pivot1) {
613 a[k] = a[less];
614 a[less++] = pivot1;
615 } else { // pivot1 < a[great] < pivot2
616 a[k] = a[great];
617 }
618 a[great--] = pivot2;
619 } else if (ak == pivot1) { // Move a[k] to left part
620 a[k] = a[less];
621 a[less++] = pivot1;
622 }
623 }
624 }
625
626 // Sort center part recursively, excluding known pivot values
627 doSort(a, less, great);
628 }
629
630 /**
631 * Sorts the specified array into ascending numerical order.
632 *
633 * @param a the array to be sorted
634 */
635 public static void sort(short[] a) {
636 doSort(a, 0, a.length - 1);
637 }
638
639 /**
640 * Sorts the specified range of the array into ascending order. The range
641 * to be sorted extends from the index {@code fromIndex}, inclusive, to
642 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
643 * the range to be sorted is empty (and the call is a no-op).
644 *
645 * @param a the array to be sorted
646 * @param fromIndex the index of the first element, inclusive, to be sorted
647 * @param toIndex the index of the last element, exclusive, to be sorted
648 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
649 * @throws ArrayIndexOutOfBoundsException
650 * if {@code fromIndex < 0} or {@code toIndex > a.length}
651 */
652 public static void sort(short[] a, int fromIndex, int toIndex) {
653 rangeCheck(a.length, fromIndex, toIndex);
654 doSort(a, fromIndex, toIndex - 1);
655 }
656
657 /** The number of distinct short values. */
658 private static final int NUM_SHORT_VALUES = 1 << 16;
659
660 /**
661 * Sorts the specified range of the array into ascending order. This
662 * method differs from the public {@code sort} method in that the
663 * {@code right} index is inclusive, and it does no range checking on
664 * {@code left} or {@code right}.
665 *
666 * @param a the array to be sorted
667 * @param left the index of the first element, inclusive, to be sorted
668 * @param right the index of the last element, inclusive, to be sorted
669 */
670 private static void doSort(short[] a, int left, int right) {
671 // Use insertion sort on tiny arrays
672 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
673 for (int i = left + 1; i <= right; i++) {
674 short ai = a[i];
675 int j;
676 for (j = i - 1; j >= left && ai < a[j]; j--) {
677 a[j + 1] = a[j];
678 }
679 a[j + 1] = ai;
680 }
681 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
682 // Use counting sort on huge arrays
683 int[] count = new int[NUM_SHORT_VALUES];
684
685 for (int i = left; i <= right; i++) {
686 count[a[i] - Short.MIN_VALUE]++;
687 }
688 for (int i = 0, k = left; i < count.length && k <= right; i++) {
689 short value = (short) (i + Short.MIN_VALUE);
690
691 for (int s = count[i]; s > 0; s--) {
692 a[k++] = value;
693 }
694 }
695 } else { // Use Dual-Pivot Quicksort on large arrays
696 dualPivotQuicksort(a, left, right);
697 }
698 }
699
700 /**
701 * Sorts the specified range of the array into ascending order by the
702 * Dual-Pivot Quicksort algorithm.
703 *
704 * @param a the array to be sorted
705 * @param left the index of the first element, inclusive, to be sorted
706 * @param right the index of the last element, inclusive, to be sorted
707 */
708 private static void dualPivotQuicksort(short[] a, int left, int right) {
709 // Compute indices of five evenly spaced elements
710 int sixth = (right - left + 1) / 6;
711 int e1 = left + sixth;
712 int e5 = right - sixth;
713 int e3 = (left + right) >>> 1; // The midpoint
714 int e4 = e3 + sixth;
715 int e2 = e3 - sixth;
716
717 // Sort these elements using a 5-element sorting network
718 short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
719
720 if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
721 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
722 if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
723 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
724 if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
725 if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
726 if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
727 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
728 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
729
730 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
731
732 /*
733 * Use the second and fourth of the five sorted elements as pivots.
734 * These values are inexpensive approximations of the first and
735 * second terciles of the array. Note that pivot1 <= pivot2.
736 *
737 * The pivots are stored in local variables, and the first and
738 * the last of the elements to be sorted are moved to the locations
739 * formerly occupied by the pivots. When partitioning is complete,
740 * the pivots are swapped back into their final positions, and
741 * excluded from subsequent sorting.
742 */
743 short pivot1 = ae2; a[e2] = a[left];
744 short pivot2 = ae4; a[e4] = a[right];
745
746 // Pointers
747 int less = left + 1; // The index of first element of center part
748 int great = right - 1; // The index before first element of right part
749
750 boolean pivotsDiffer = (pivot1 != pivot2);
751
752 if (pivotsDiffer) {
753 /*
754 * Partitioning:
755 *
756 * left part center part right part
757 * +------------------------------------------------------------+
758 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
759 * +------------------------------------------------------------+
760 * ^ ^ ^
761 * | | |
762 * less k great
763 *
764 * Invariants:
765 *
766 * all in (left, less) < pivot1
767 * pivot1 <= all in [less, k) <= pivot2
768 * all in (great, right) > pivot2
769 *
770 * Pointer k is the first index of ?-part
771 */
772 outer:
773 for (int k = less; k <= great; k++) {
774 short ak = a[k];
775 if (ak < pivot1) { // Move a[k] to left part
776 if (k != less) {
777 a[k] = a[less];
778 a[less] = ak;
779 }
780 less++;
781 } else if (ak > pivot2) { // Move a[k] to right part
782 while (a[great] > pivot2) {
783 if (great-- == k) {
784 break outer;
785 }
786 }
787 if (a[great] < pivot1) {
788 a[k] = a[less];
789 a[less++] = a[great];
790 a[great--] = ak;
791 } else { // pivot1 <= a[great] <= pivot2
792 a[k] = a[great];
793 a[great--] = ak;
794 }
795 }
796 }
797 } else { // Pivots are equal
798 /*
799 * Partition degenerates to the traditional 3-way,
800 * or "Dutch National Flag", partition:
801 *
802 * left part center part right part
803 * +----------------------------------------------+
804 * | < pivot | == pivot | ? | > pivot |
805 * +----------------------------------------------+
806 * ^ ^ ^
807 * | | |
808 * less k great
809 *
810 * Invariants:
811 *
812 * all in (left, less) < pivot
813 * all in [less, k) == pivot
814 * all in (great, right) > pivot
815 *
816 * Pointer k is the first index of ?-part
817 */
818 for (int k = less; k <= great; k++) {
819 short ak = a[k];
820 if (ak == pivot1) {
821 continue;
822 }
823 if (ak < pivot1) { // Move a[k] to left part
824 if (k != less) {
825 a[k] = a[less];
826 a[less] = ak;
827 }
828 less++;
829 } else { // (a[k] > pivot1) - Move a[k] to right part
830 /*
831 * We know that pivot1 == a[e3] == pivot2. Thus, we know
832 * that great will still be >= k when the following loop
833 * terminates, even though we don't test for it explicitly.
834 * In other words, a[e3] acts as a sentinel for great.
835 */
836 while (a[great] > pivot1) {
837 great--;
838 }
839 if (a[great] < pivot1) {
840 a[k] = a[less];
841 a[less++] = a[great];
842 a[great--] = ak;
843 } else { // a[great] == pivot1
844 a[k] = pivot1;
845 a[great--] = ak;
846 }
847 }
848 }
849 }
850
851 // Swap pivots into their final positions
852 a[left] = a[less - 1]; a[less - 1] = pivot1;
853 a[right] = a[great + 1]; a[great + 1] = pivot2;
854
855 // Sort left and right parts recursively, excluding known pivot values
856 doSort(a, left, less - 2);
857 doSort(a, great + 2, right);
858
859 /*
860 * If pivot1 == pivot2, all elements from center
861 * part are equal and, therefore, already sorted
862 */
863 if (!pivotsDiffer) {
864 return;
865 }
866
867 /*
868 * If center part is too large (comprises > 2/3 of the array),
869 * swap internal pivot values to ends
870 */
871 if (less < e1 && great > e5) {
872 while (a[less] == pivot1) {
873 less++;
874 }
875 while (a[great] == pivot2) {
876 great--;
877 }
878
879 /*
880 * Partitioning:
881 *
882 * left part center part right part
883 * +----------------------------------------------------------+
884 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
885 * +----------------------------------------------------------+
886 * ^ ^ ^
887 * | | |
888 * less k great
889 *
890 * Invariants:
891 *
892 * all in (*, less) == pivot1
893 * pivot1 < all in [less, k) < pivot2
894 * all in (great, *) == pivot2
895 *
896 * Pointer k is the first index of ?-part
897 */
898 outer:
899 for (int k = less; k <= great; k++) {
900 short ak = a[k];
901 if (ak == pivot2) { // Move a[k] to right part
902 while (a[great] == pivot2) {
903 if (great-- == k) {
904 break outer;
905 }
906 }
907 if (a[great] == pivot1) {
908 a[k] = a[less];
909 a[less++] = pivot1;
910 } else { // pivot1 < a[great] < pivot2
911 a[k] = a[great];
912 }
913 a[great--] = pivot2;
914 } else if (ak == pivot1) { // Move a[k] to left part
915 a[k] = a[less];
916 a[less++] = pivot1;
917 }
918 }
919 }
920
921 // Sort center part recursively, excluding known pivot values
922 doSort(a, less, great);
923 }
924
925 /**
926 * Sorts the specified array into ascending numerical order.
927 *
928 * @param a the array to be sorted
929 */
930 public static void sort(char[] a) {
931 doSort(a, 0, a.length - 1);
932 }
933
934 /**
935 * Sorts the specified range of the array into ascending order. The range
936 * to be sorted extends from the index {@code fromIndex}, inclusive, to
937 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
938 * the range to be sorted is empty (and the call is a no-op).
939 *
940 * @param a the array to be sorted
941 * @param fromIndex the index of the first element, inclusive, to be sorted
942 * @param toIndex the index of the last element, exclusive, to be sorted
943 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
944 * @throws ArrayIndexOutOfBoundsException
945 * if {@code fromIndex < 0} or {@code toIndex > a.length}
946 */
947 public static void sort(char[] a, int fromIndex, int toIndex) {
948 rangeCheck(a.length, fromIndex, toIndex);
949 doSort(a, fromIndex, toIndex - 1);
950 }
951
952 /** The number of distinct char values. */
953 private static final int NUM_CHAR_VALUES = 1 << 16;
954
955 /**
956 * Sorts the specified range of the array into ascending order. This
957 * method differs from the public {@code sort} method in that the
958 * {@code right} index is inclusive, and it does no range checking on
959 * {@code left} or {@code right}.
960 *
961 * @param a the array to be sorted
962 * @param left the index of the first element, inclusive, to be sorted
963 * @param right the index of the last element, inclusive, to be sorted
964 */
965 private static void doSort(char[] a, int left, int right) {
966 // Use insertion sort on tiny arrays
967 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
968 for (int i = left + 1; i <= right; i++) {
969 char ai = a[i];
970 int j;
971 for (j = i - 1; j >= left && ai < a[j]; j--) {
972 a[j + 1] = a[j];
973 }
974 a[j + 1] = ai;
975 }
976 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
977 // Use counting sort on huge arrays
978 int[] count = new int[NUM_CHAR_VALUES];
979
980 for (int i = left; i <= right; i++) {
981 count[a[i]]++;
982 }
983 for (int i = 0, k = left; i < count.length && k <= right; i++) {
984 for (int s = count[i]; s > 0; s--) {
985 a[k++] = (char) i;
986 }
987 }
988 } else { // Use Dual-Pivot Quicksort on large arrays
989 dualPivotQuicksort(a, left, right);
990 }
991 }
992
993 /**
994 * Sorts the specified range of the array into ascending order by the
995 * Dual-Pivot Quicksort algorithm.
996 *
997 * @param a the array to be sorted
998 * @param left the index of the first element, inclusive, to be sorted
999 * @param right the index of the last element, inclusive, to be sorted
1000 */
1001 private static void dualPivotQuicksort(char[] a, int left, int right) {
1002 // Compute indices of five evenly spaced elements
1003 int sixth = (right - left + 1) / 6;
1004 int e1 = left + sixth;
1005 int e5 = right - sixth;
1006 int e3 = (left + right) >>> 1; // The midpoint
1007 int e4 = e3 + sixth;
1008 int e2 = e3 - sixth;
1009
1010 // Sort these elements using a 5-element sorting network
1011 char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1012
1013 if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
1014 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
1015 if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
1016 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
1017 if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
1018 if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
1019 if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
1020 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
1021 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
1022
1023 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1024
1025 /*
1026 * Use the second and fourth of the five sorted elements as pivots.
1027 * These values are inexpensive approximations of the first and
1028 * second terciles of the array. Note that pivot1 <= pivot2.
1029 *
1030 * The pivots are stored in local variables, and the first and
1031 * the last of the elements to be sorted are moved to the locations
1032 * formerly occupied by the pivots. When partitioning is complete,
1033 * the pivots are swapped back into their final positions, and
1034 * excluded from subsequent sorting.
1035 */
1036 char pivot1 = ae2; a[e2] = a[left];
1037 char pivot2 = ae4; a[e4] = a[right];
1038
1039 // Pointers
1040 int less = left + 1; // The index of first element of center part
1041 int great = right - 1; // The index before first element of right part
1042
1043 boolean pivotsDiffer = (pivot1 != pivot2);
1044
1045 if (pivotsDiffer) {
1046 /*
1047 * Partitioning:
1048 *
1049 * left part center part right part
1050 * +------------------------------------------------------------+
1051 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1052 * +------------------------------------------------------------+
1053 * ^ ^ ^
1054 * | | |
1055 * less k great
1056 *
1057 * Invariants:
1058 *
1059 * all in (left, less) < pivot1
1060 * pivot1 <= all in [less, k) <= pivot2
1061 * all in (great, right) > pivot2
1062 *
1063 * Pointer k is the first index of ?-part
1064 */
1065 outer:
1066 for (int k = less; k <= great; k++) {
1067 char ak = a[k];
1068 if (ak < pivot1) { // Move a[k] to left part
1069 if (k != less) {
1070 a[k] = a[less];
1071 a[less] = ak;
1072 }
1073 less++;
1074 } else if (ak > pivot2) { // Move a[k] to right part
1075 while (a[great] > pivot2) {
1076 if (great-- == k) {
1077 break outer;
1078 }
1079 }
1080 if (a[great] < pivot1) {
1081 a[k] = a[less];
1082 a[less++] = a[great];
1083 a[great--] = ak;
1084 } else { // pivot1 <= a[great] <= pivot2
1085 a[k] = a[great];
1086 a[great--] = ak;
1087 }
1088 }
1089 }
1090 } else { // Pivots are equal
1091 /*
1092 * Partition degenerates to the traditional 3-way,
1093 * or "Dutch National Flag", partition:
1094 *
1095 * left part center part right part
1096 * +----------------------------------------------+
1097 * | < pivot | == pivot | ? | > pivot |
1098 * +----------------------------------------------+
1099 * ^ ^ ^
1100 * | | |
1101 * less k great
1102 *
1103 * Invariants:
1104 *
1105 * all in (left, less) < pivot
1106 * all in [less, k) == pivot
1107 * all in (great, right) > pivot
1108 *
1109 * Pointer k is the first index of ?-part
1110 */
1111 for (int k = less; k <= great; k++) {
1112 char ak = a[k];
1113 if (ak == pivot1) {
1114 continue;
1115 }
1116 if (ak < pivot1) { // Move a[k] to left part
1117 if (k != less) {
1118 a[k] = a[less];
1119 a[less] = ak;
1120 }
1121 less++;
1122 } else { // (a[k] > pivot1) - Move a[k] to right part
1123 /*
1124 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1125 * that great will still be >= k when the following loop
1126 * terminates, even though we don't test for it explicitly.
1127 * In other words, a[e3] acts as a sentinel for great.
1128 */
1129 while (a[great] > pivot1) {
1130 great--;
1131 }
1132 if (a[great] < pivot1) {
1133 a[k] = a[less];
1134 a[less++] = a[great];
1135 a[great--] = ak;
1136 } else { // a[great] == pivot1
1137 a[k] = pivot1;
1138 a[great--] = ak;
1139 }
1140 }
1141 }
1142 }
1143
1144 // Swap pivots into their final positions
1145 a[left] = a[less - 1]; a[less - 1] = pivot1;
1146 a[right] = a[great + 1]; a[great + 1] = pivot2;
1147
1148 // Sort left and right parts recursively, excluding known pivot values
1149 doSort(a, left, less - 2);
1150 doSort(a, great + 2, right);
1151
1152 /*
1153 * If pivot1 == pivot2, all elements from center
1154 * part are equal and, therefore, already sorted
1155 */
1156 if (!pivotsDiffer) {
1157 return;
1158 }
1159
1160 /*
1161 * If center part is too large (comprises > 2/3 of the array),
1162 * swap internal pivot values to ends
1163 */
1164 if (less < e1 && great > e5) {
1165 while (a[less] == pivot1) {
1166 less++;
1167 }
1168 while (a[great] == pivot2) {
1169 great--;
1170 }
1171
1172 /*
1173 * Partitioning:
1174 *
1175 * left part center part right part
1176 * +----------------------------------------------------------+
1177 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1178 * +----------------------------------------------------------+
1179 * ^ ^ ^
1180 * | | |
1181 * less k great
1182 *
1183 * Invariants:
1184 *
1185 * all in (*, less) == pivot1
1186 * pivot1 < all in [less, k) < pivot2
1187 * all in (great, *) == pivot2
1188 *
1189 * Pointer k is the first index of ?-part
1190 */
1191 outer:
1192 for (int k = less; k <= great; k++) {
1193 char ak = a[k];
1194 if (ak == pivot2) { // Move a[k] to right part
1195 while (a[great] == pivot2) {
1196 if (great-- == k) {
1197 break outer;
1198 }
1199 }
1200 if (a[great] == pivot1) {
1201 a[k] = a[less];
1202 a[less++] = pivot1;
1203 } else { // pivot1 < a[great] < pivot2
1204 a[k] = a[great];
1205 }
1206 a[great--] = pivot2;
1207 } else if (ak == pivot1) { // Move a[k] to left part
1208 a[k] = a[less];
1209 a[less++] = pivot1;
1210 }
1211 }
1212 }
1213
1214 // Sort center part recursively, excluding known pivot values
1215 doSort(a, less, great);
1216 }
1217
1218 /**
1219 * Sorts the specified array into ascending numerical order.
1220 *
1221 * @param a the array to be sorted
1222 */
1223 public static void sort(byte[] a) {
1224 doSort(a, 0, a.length - 1);
1225 }
1226
1227 /**
1228 * Sorts the specified range of the array into ascending order. The range
1229 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1230 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1231 * the range to be sorted is empty (and the call is a no-op).
1232 *
1233 * @param a the array to be sorted
1234 * @param fromIndex the index of the first element, inclusive, to be sorted
1235 * @param toIndex the index of the last element, exclusive, to be sorted
1236 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1237 * @throws ArrayIndexOutOfBoundsException
1238 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1239 */
1240 public static void sort(byte[] a, int fromIndex, int toIndex) {
1241 rangeCheck(a.length, fromIndex, toIndex);
1242 doSort(a, fromIndex, toIndex - 1);
1243 }
1244
1245 /** The number of distinct byte values. */
1246 private static final int NUM_BYTE_VALUES = 1 << 8;
1247
1248 /**
1249 * Sorts the specified range of the array into ascending order. This
1250 * method differs from the public {@code sort} method in that the
1251 * {@code right} index is inclusive, and it does no range checking on
1252 * {@code left} or {@code right}.
1253 *
1254 * @param a the array to be sorted
1255 * @param left the index of the first element, inclusive, to be sorted
1256 * @param right the index of the last element, inclusive, to be sorted
1257 */
1258 private static void doSort(byte[] a, int left, int right) {
1259 // Use insertion sort on tiny arrays
1260 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1261 for (int i = left + 1; i <= right; i++) {
1262 byte ai = a[i];
1263 int j;
1264 for (j = i - 1; j >= left && ai < a[j]; j--) {
1265 a[j + 1] = a[j];
1266 }
1267 a[j + 1] = ai;
1268 }
1269 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
1270 // Use counting sort on huge arrays
1271 int[] count = new int[NUM_BYTE_VALUES];
1272
1273 for (int i = left; i <= right; i++) {
1274 count[a[i] - Byte.MIN_VALUE]++;
1275 }
1276 for (int i = 0, k = left; i < count.length && k <= right; i++) {
1277 byte value = (byte) (i + Byte.MIN_VALUE);
1278
1279 for (int s = count[i]; s > 0; s--) {
1280 a[k++] = value;
1281 }
1282 }
1283 } else { // Use Dual-Pivot Quicksort on large arrays
1284 dualPivotQuicksort(a, left, right);
1285 }
1286 }
1287
1288 /**
1289 * Sorts the specified range of the array into ascending order by the
1290 * Dual-Pivot Quicksort algorithm.
1291 *
1292 * @param a the array to be sorted
1293 * @param left the index of the first element, inclusive, to be sorted
1294 * @param right the index of the last element, inclusive, to be sorted
1295 */
1296 private static void dualPivotQuicksort(byte[] a, int left, int right) {
1297 // Compute indices of five evenly spaced elements
1298 int sixth = (right - left + 1) / 6;
1299 int e1 = left + sixth;
1300 int e5 = right - sixth;
1301 int e3 = (left + right) >>> 1; // The midpoint
1302 int e4 = e3 + sixth;
1303 int e2 = e3 - sixth;
1304
1305 // Sort these elements using a 5-element sorting network
1306 byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1307
1308 if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
1309 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1310 if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
1311 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1312 if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
1313 if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
1314 if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
1315 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1316 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1317
1318 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1319
1320 /*
1321 * Use the second and fourth of the five sorted elements as pivots.
1322 * These values are inexpensive approximations of the first and
1323 * second terciles of the array. Note that pivot1 <= pivot2.
1324 *
1325 * The pivots are stored in local variables, and the first and
1326 * the last of the elements to be sorted are moved to the locations
1327 * formerly occupied by the pivots. When partitioning is complete,
1328 * the pivots are swapped back into their final positions, and
1329 * excluded from subsequent sorting.
1330 */
1331 byte pivot1 = ae2; a[e2] = a[left];
1332 byte pivot2 = ae4; a[e4] = a[right];
1333
1334 // Pointers
1335 int less = left + 1; // The index of first element of center part
1336 int great = right - 1; // The index before first element of right part
1337
1338 boolean pivotsDiffer = (pivot1 != pivot2);
1339
1340 if (pivotsDiffer) {
1341 /*
1342 * Partitioning:
1343 *
1344 * left part center part right part
1345 * +------------------------------------------------------------+
1346 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1347 * +------------------------------------------------------------+
1348 * ^ ^ ^
1349 * | | |
1350 * less k great
1351 *
1352 * Invariants:
1353 *
1354 * all in (left, less) < pivot1
1355 * pivot1 <= all in [less, k) <= pivot2
1356 * all in (great, right) > pivot2
1357 *
1358 * Pointer k is the first index of ?-part
1359 */
1360 outer:
1361 for (int k = less; k <= great; k++) {
1362 byte ak = a[k];
1363 if (ak < pivot1) { // Move a[k] to left part
1364 if (k != less) {
1365 a[k] = a[less];
1366 a[less] = ak;
1367 }
1368 less++;
1369 } else if (ak > pivot2) { // Move a[k] to right part
1370 while (a[great] > pivot2) {
1371 if (great-- == k) {
1372 break outer;
1373 }
1374 }
1375 if (a[great] < pivot1) {
1376 a[k] = a[less];
1377 a[less++] = a[great];
1378 a[great--] = ak;
1379 } else { // pivot1 <= a[great] <= pivot2
1380 a[k] = a[great];
1381 a[great--] = ak;
1382 }
1383 }
1384 }
1385 } else { // Pivots are equal
1386 /*
1387 * Partition degenerates to the traditional 3-way,
1388 * or "Dutch National Flag", partition:
1389 *
1390 * left part center part right part
1391 * +----------------------------------------------+
1392 * | < pivot | == pivot | ? | > pivot |
1393 * +----------------------------------------------+
1394 * ^ ^ ^
1395 * | | |
1396 * less k great
1397 *
1398 * Invariants:
1399 *
1400 * all in (left, less) < pivot
1401 * all in [less, k) == pivot
1402 * all in (great, right) > pivot
1403 *
1404 * Pointer k is the first index of ?-part
1405 */
1406 for (int k = less; k <= great; k++) {
1407 byte ak = a[k];
1408 if (ak == pivot1) {
1409 continue;
1410 }
1411 if (ak < pivot1) { // Move a[k] to left part
1412 if (k != less) {
1413 a[k] = a[less];
1414 a[less] = ak;
1415 }
1416 less++;
1417 } else { // (a[k] > pivot1) - Move a[k] to right part
1418 /*
1419 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1420 * that great will still be >= k when the following loop
1421 * terminates, even though we don't test for it explicitly.
1422 * In other words, a[e3] acts as a sentinel for great.
1423 */
1424 while (a[great] > pivot1) {
1425 great--;
1426 }
1427 if (a[great] < pivot1) {
1428 a[k] = a[less];
1429 a[less++] = a[great];
1430 a[great--] = ak;
1431 } else { // a[great] == pivot1
1432 a[k] = pivot1;
1433 a[great--] = ak;
1434 }
1435 }
1436 }
1437 }
1438
1439 // Swap pivots into their final positions
1440 a[left] = a[less - 1]; a[less - 1] = pivot1;
1441 a[right] = a[great + 1]; a[great + 1] = pivot2;
1442
1443 // Sort left and right parts recursively, excluding known pivot values
1444 doSort(a, left, less - 2);
1445 doSort(a, great + 2, right);
1446
1447 /*
1448 * If pivot1 == pivot2, all elements from center
1449 * part are equal and, therefore, already sorted
1450 */
1451 if (!pivotsDiffer) {
1452 return;
1453 }
1454
1455 /*
1456 * If center part is too large (comprises > 2/3 of the array),
1457 * swap internal pivot values to ends
1458 */
1459 if (less < e1 && great > e5) {
1460 while (a[less] == pivot1) {
1461 less++;
1462 }
1463 while (a[great] == pivot2) {
1464 great--;
1465 }
1466
1467 /*
1468 * Partitioning:
1469 *
1470 * left part center part right part
1471 * +----------------------------------------------------------+
1472 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1473 * +----------------------------------------------------------+
1474 * ^ ^ ^
1475 * | | |
1476 * less k great
1477 *
1478 * Invariants:
1479 *
1480 * all in (*, less) == pivot1
1481 * pivot1 < all in [less, k) < pivot2
1482 * all in (great, *) == pivot2
1483 *
1484 * Pointer k is the first index of ?-part
1485 */
1486 outer:
1487 for (int k = less; k <= great; k++) {
1488 byte ak = a[k];
1489 if (ak == pivot2) { // Move a[k] to right part
1490 while (a[great] == pivot2) {
1491 if (great-- == k) {
1492 break outer;
1493 }
1494 }
1495 if (a[great] == pivot1) {
1496 a[k] = a[less];
1497 a[less++] = pivot1;
1498 } else { // pivot1 < a[great] < pivot2
1499 a[k] = a[great];
1500 }
1501 a[great--] = pivot2;
1502 } else if (ak == pivot1) { // Move a[k] to left part
1503 a[k] = a[less];
1504 a[less++] = pivot1;
1505 }
1506 }
1507 }
1508
1509 // Sort center part recursively, excluding known pivot values
1510 doSort(a, less, great);
1511 }
1512
1513 /**
1514 * Sorts the specified array into ascending numerical order.
1515 *
1516 * <p>The {@code <} relation does not provide a total order on all float
1517 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1518 * value compares neither less than, greater than, nor equal to any value,
1519 * even itself. This method uses the total order imposed by the method
1520 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1521 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1522 * other value and all {@code Float.NaN} values are considered equal.
1523 *
1524 * @param a the array to be sorted
1525 */
1526 public static void sort(float[] a) {
1527 sortNegZeroAndNaN(a, 0, a.length - 1);
1528 }
1529
1530 /**
1531 * Sorts the specified range of the array into ascending order. The range
1532 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1533 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1534 * the range to be sorted is empty and the call is a no-op).
1535 *
1536 * <p>The {@code <} relation does not provide a total order on all float
1537 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1538 * value compares neither less than, greater than, nor equal to any value,
1539 * even itself. This method uses the total order imposed by the method
1540 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1541 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1542 * other value and all {@code Float.NaN} values are considered equal.
1543 *
1544 * @param a the array to be sorted
1545 * @param fromIndex the index of the first element, inclusive, to be sorted
1546 * @param toIndex the index of the last element, exclusive, to be sorted
1547 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1548 * @throws ArrayIndexOutOfBoundsException
1549 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1550 */
1551 public static void sort(float[] a, int fromIndex, int toIndex) {
1552 rangeCheck(a.length, fromIndex, toIndex);
1553 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
1554 }
1555
1556 /**
1557 * Sorts the specified range of the array into ascending order. The
1558 * sort is done in three phases to avoid expensive comparisons in the
1559 * inner loop. The comparisons would be expensive due to anomalies
1560 * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
1561 *
1562 * @param a the array to be sorted
1563 * @param left the index of the first element, inclusive, to be sorted
1564 * @param right the index of the last element, inclusive, to be sorted
1565 */
1566 private static void sortNegZeroAndNaN(float[] a, int left, int right) {
1567 /*
1568 * Phase 1: Count negative zeros and move NaNs to end of array
1569 */
1570 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
1571 int numNegativeZeros = 0;
1572 int n = right;
1573
1574 for (int k = left; k <= n; k++) {
1575 float ak = a[k];
1576 if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
1577 a[k] = 0.0f;
1578 numNegativeZeros++;
1579 } else if (ak != ak) { // i.e., ak is NaN
1580 a[k--] = a[n];
1581 a[n--] = Float.NaN;
1582 }
1583 }
1584
1585 /*
1586 * Phase 2: Sort everything except NaNs (which are already in place)
1587 */
1588 doSort(a, left, n);
1589
1590 /*
1591 * Phase 3: Turn positive zeros back into negative zeros as appropriate
1592 */
1593 if (numNegativeZeros == 0) {
1594 return;
1595 }
1596
1597 // Find first zero element
1598 int zeroIndex = findAnyZero(a, left, n);
1599
1600 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
1601 zeroIndex = i;
1602 }
1603
1604 // Turn the right number of positive zeros back into negative zeros
1605 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
1606 a[i] = -0.0f;
1607 }
1608 }
1609
1610 /**
1611 * Returns the index of some zero element in the specified range via
1615 * @param a the array to be searched
1616 * @param low the index of the first element, inclusive, to be searched
1617 * @param high the index of the last element, inclusive, to be searched
1618 */
1619 private static int findAnyZero(float[] a, int low, int high) {
1620 while (true) {
1621 int middle = (low + high) >>> 1;
1622 float middleValue = a[middle];
1623
1624 if (middleValue < 0.0f) {
1625 low = middle + 1;
1626 } else if (middleValue > 0.0f) {
1627 high = middle - 1;
1628 } else { // middleValue == 0.0f
1629 return middle;
1630 }
1631 }
1632 }
1633
1634 /**
1635 * Sorts the specified range of the array into ascending order. This
1636 * method differs from the public {@code sort} method in three ways:
1637 * {@code right} index is inclusive, it does no range checking on
1638 * {@code left} or {@code right}, and it does not handle negative
1639 * zeros or NaNs in the array.
1640 *
1641 * @param a the array to be sorted, which must not contain -0.0f or NaN
1642 * @param left the index of the first element, inclusive, to be sorted
1643 * @param right the index of the last element, inclusive, to be sorted
1644 */
1645 private static void doSort(float[] a, int left, int right) {
1646 // Use insertion sort on tiny arrays
1647 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1648 for (int i = left + 1; i <= right; i++) {
1649 float ai = a[i];
1650 int j;
1651 for (j = i - 1; j >= left && ai < a[j]; j--) {
1652 a[j + 1] = a[j];
1653 }
1654 a[j + 1] = ai;
1655 }
1656 } else { // Use Dual-Pivot Quicksort on large arrays
1657 dualPivotQuicksort(a, left, right);
1658 }
1659 }
1660
1661 /**
1662 * Sorts the specified range of the array into ascending order by the
1663 * Dual-Pivot Quicksort algorithm.
1664 *
1665 * @param a the array to be sorted
1666 * @param left the index of the first element, inclusive, to be sorted
1667 * @param right the index of the last element, inclusive, to be sorted
1668 */
1669 private static void dualPivotQuicksort(float[] a, int left, int right) {
1670 // Compute indices of five evenly spaced elements
1671 int sixth = (right - left + 1) / 6;
1672 int e1 = left + sixth;
1673 int e5 = right - sixth;
1674 int e3 = (left + right) >>> 1; // The midpoint
1675 int e4 = e3 + sixth;
1676 int e2 = e3 - sixth;
1677
1678 // Sort these elements using a 5-element sorting network
1679 float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1680
1681 if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
1682 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1683 if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
1684 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1685 if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
1686 if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
1687 if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
1688 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1689 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1690
1691 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1692
1693 /*
1694 * Use the second and fourth of the five sorted elements as pivots.
1695 * These values are inexpensive approximations of the first and
1696 * second terciles of the array. Note that pivot1 <= pivot2.
1697 *
1698 * The pivots are stored in local variables, and the first and
1699 * the last of the elements to be sorted are moved to the locations
1700 * formerly occupied by the pivots. When partitioning is complete,
1701 * the pivots are swapped back into their final positions, and
1702 * excluded from subsequent sorting.
1703 */
1704 float pivot1 = ae2; a[e2] = a[left];
1705 float pivot2 = ae4; a[e4] = a[right];
1706
1707 // Pointers
1708 int less = left + 1; // The index of first element of center part
1709 int great = right - 1; // The index before first element of right part
1710
1711 boolean pivotsDiffer = (pivot1 != pivot2);
1712
1713 if (pivotsDiffer) {
1714 /*
1715 * Partitioning:
1716 *
1717 * left part center part right part
1718 * +------------------------------------------------------------+
1719 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1720 * +------------------------------------------------------------+
1721 * ^ ^ ^
1722 * | | |
1723 * less k great
1724 *
1725 * Invariants:
1726 *
1727 * all in (left, less) < pivot1
1728 * pivot1 <= all in [less, k) <= pivot2
1729 * all in (great, right) > pivot2
1730 *
1731 * Pointer k is the first index of ?-part
1732 */
1733 outer:
1734 for (int k = less; k <= great; k++) {
1735 float ak = a[k];
1736 if (ak < pivot1) { // Move a[k] to left part
1737 if (k != less) {
1738 a[k] = a[less];
1739 a[less] = ak;
1740 }
1741 less++;
1742 } else if (ak > pivot2) { // Move a[k] to right part
1743 while (a[great] > pivot2) {
1744 if (great-- == k) {
1745 break outer;
1746 }
1747 }
1748 if (a[great] < pivot1) {
1749 a[k] = a[less];
1750 a[less++] = a[great];
1751 a[great--] = ak;
1752 } else { // pivot1 <= a[great] <= pivot2
1753 a[k] = a[great];
1754 a[great--] = ak;
1755 }
1756 }
1757 }
1758 } else { // Pivots are equal
1759 /*
1760 * Partition degenerates to the traditional 3-way,
1761 * or "Dutch National Flag", partition:
1762 *
1763 * left part center part right part
1764 * +----------------------------------------------+
1765 * | < pivot | == pivot | ? | > pivot |
1766 * +----------------------------------------------+
1767 * ^ ^ ^
1768 * | | |
1769 * less k great
1770 *
1771 * Invariants:
1772 *
1773 * all in (left, less) < pivot
1774 * all in [less, k) == pivot
1775 * all in (great, right) > pivot
1776 *
1777 * Pointer k is the first index of ?-part
1778 */
1779 for (int k = less; k <= great; k++) {
1780 float ak = a[k];
1781 if (ak == pivot1) {
1782 continue;
1783 }
1784 if (ak < pivot1) { // Move a[k] to left part
1785 if (k != less) {
1786 a[k] = a[less];
1787 a[less] = ak;
1788 }
1789 less++;
1790 } else { // (a[k] > pivot1) - Move a[k] to right part
1791 /*
1792 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1793 * that great will still be >= k when the following loop
1794 * terminates, even though we don't test for it explicitly.
1795 * In other words, a[e3] acts as a sentinel for great.
1796 */
1797 while (a[great] > pivot1) {
1798 great--;
1799 }
1800 if (a[great] < pivot1) {
1801 a[k] = a[less];
1802 a[less++] = a[great];
1803 a[great--] = ak;
1804 } else { // a[great] == pivot1
1805 a[k] = pivot1;
1806 a[great--] = ak;
1807 }
1808 }
1809 }
1810 }
1811
1812 // Swap pivots into their final positions
1813 a[left] = a[less - 1]; a[less - 1] = pivot1;
1814 a[right] = a[great + 1]; a[great + 1] = pivot2;
1815
1816 // Sort left and right parts recursively, excluding known pivot values
1817 doSort(a, left, less - 2);
1818 doSort(a, great + 2, right);
1819
1820 /*
1821 * If pivot1 == pivot2, all elements from center
1822 * part are equal and, therefore, already sorted
1823 */
1824 if (!pivotsDiffer) {
1825 return;
1826 }
1827
1828 /*
1829 * If center part is too large (comprises > 2/3 of the array),
1830 * swap internal pivot values to ends
1831 */
1832 if (less < e1 && great > e5) {
1833 while (a[less] == pivot1) {
1834 less++;
1835 }
1836 while (a[great] == pivot2) {
1837 great--;
1838 }
1839
1840 /*
1841 * Partitioning:
1842 *
1843 * left part center part right part
1844 * +----------------------------------------------------------+
1845 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1846 * +----------------------------------------------------------+
1847 * ^ ^ ^
1848 * | | |
1849 * less k great
1850 *
1851 * Invariants:
1852 *
1853 * all in (*, less) == pivot1
1854 * pivot1 < all in [less, k) < pivot2
1855 * all in (great, *) == pivot2
1856 *
1857 * Pointer k is the first index of ?-part
1858 */
1859 outer:
1860 for (int k = less; k <= great; k++) {
1861 float ak = a[k];
1862 if (ak == pivot2) { // Move a[k] to right part
1863 while (a[great] == pivot2) {
1864 if (great-- == k) {
1865 break outer;
1866 }
1867 }
1868 if (a[great] == pivot1) {
1869 a[k] = a[less];
1870 a[less++] = pivot1;
1871 } else { // pivot1 < a[great] < pivot2
1872 a[k] = a[great];
1873 }
1874 a[great--] = pivot2;
1875 } else if (ak == pivot1) { // Move a[k] to left part
1876 a[k] = a[less];
1877 a[less++] = pivot1;
1878 }
1879 }
1880 }
1881
1882 // Sort center part recursively, excluding known pivot values
1883 doSort(a, less, great);
1884 }
1885
1886 /**
1887 * Sorts the specified array into ascending numerical order.
1888 *
1889 * <p>The {@code <} relation does not provide a total order on all double
1890 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1891 * value compares neither less than, greater than, nor equal to any value,
1892 * even itself. This method uses the total order imposed by the method
1893 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1894 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1895 * other value and all {@code Double.NaN} values are considered equal.
1896 *
1897 * @param a the array to be sorted
1898 */
1899 public static void sort(double[] a) {
1900 sortNegZeroAndNaN(a, 0, a.length - 1);
1901 }
1902
1903 /**
1904 * Sorts the specified range of the array into ascending order. The range
1905 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1921 * @throws ArrayIndexOutOfBoundsException
1922 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1923 */
1924 public static void sort(double[] a, int fromIndex, int toIndex) {
1925 rangeCheck(a.length, fromIndex, toIndex);
1926 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
1927 }
1928
1929 /**
1930 * Sorts the specified range of the array into ascending order. The
1931 * sort is done in three phases to avoid expensive comparisons in the
1932 * inner loop. The comparisons would be expensive due to anomalies
1933 * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
1934 *
1935 * @param a the array to be sorted
1936 * @param left the index of the first element, inclusive, to be sorted
1937 * @param right the index of the last element, inclusive, to be sorted
1938 */
1939 private static void sortNegZeroAndNaN(double[] a, int left, int right) {
1940 /*
1941 * Phase 1: Count negative zeros and move NaNs to end of array
1942 */
1943 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
1944 int numNegativeZeros = 0;
1945 int n = right;
1946
1947 for (int k = left; k <= n; k++) {
1948 double ak = a[k];
1949 if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
1950 a[k] = 0.0d;
1951 numNegativeZeros++;
1952 } else if (ak != ak) { // i.e., ak is NaN
1953 a[k--] = a[n];
1954 a[n--] = Double.NaN;
1955 }
1956 }
1957
1958 /*
1959 * Phase 2: Sort everything except NaNs (which are already in place)
1960 */
1961 doSort(a, left, n);
1962
1963 /*
1964 * Phase 3: Turn positive zeros back into negative zeros as appropriate
1965 */
1966 if (numNegativeZeros == 0) {
1967 return;
1968 }
1969
1970 // Find first zero element
1971 int zeroIndex = findAnyZero(a, left, n);
1972
1973 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
1974 zeroIndex = i;
1975 }
1976
1977 // Turn the right number of positive zeros back into negative zeros
1978 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
1979 a[i] = -0.0d;
1980 }
1981 }
1982
1983 /**
1984 * Returns the index of some zero element in the specified range via
1988 * @param a the array to be searched
1989 * @param low the index of the first element, inclusive, to be searched
1990 * @param high the index of the last element, inclusive, to be searched
1991 */
1992 private static int findAnyZero(double[] a, int low, int high) {
1993 while (true) {
1994 int middle = (low + high) >>> 1;
1995 double middleValue = a[middle];
1996
1997 if (middleValue < 0.0d) {
1998 low = middle + 1;
1999 } else if (middleValue > 0.0d) {
2000 high = middle - 1;
2001 } else { // middleValue == 0.0d
2002 return middle;
2003 }
2004 }
2005 }
2006
2007 /**
2008 * Sorts the specified range of the array into ascending order. This
2009 * method differs from the public {@code sort} method in three ways:
2010 * {@code right} index is inclusive, it does no range checking on
2011 * {@code left} or {@code right}, and it does not handle negative
2012 * zeros or NaNs in the array.
2013 *
2014 * @param a the array to be sorted, which must not contain -0.0d and NaN
2015 * @param left the index of the first element, inclusive, to be sorted
2016 * @param right the index of the last element, inclusive, to be sorted
2017 */
2018 private static void doSort(double[] a, int left, int right) {
2019 // Use insertion sort on tiny arrays
2020 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
2021 for (int i = left + 1; i <= right; i++) {
2022 double ai = a[i];
2023 int j;
2024 for (j = i - 1; j >= left && ai < a[j]; j--) {
2025 a[j + 1] = a[j];
2026 }
2027 a[j + 1] = ai;
2028 }
2029 } else { // Use Dual-Pivot Quicksort on large arrays
2030 dualPivotQuicksort(a, left, right);
2031 }
2032 }
2033
2034 /**
2035 * Sorts the specified range of the array into ascending order by the
2036 * Dual-Pivot Quicksort algorithm.
2037 *
2038 * @param a the array to be sorted
2039 * @param left the index of the first element, inclusive, to be sorted
2040 * @param right the index of the last element, inclusive, to be sorted
2041 */
2042 private static void dualPivotQuicksort(double[] a, int left, int right) {
2043 // Compute indices of five evenly spaced elements
2044 int sixth = (right - left + 1) / 6;
2045 int e1 = left + sixth;
2046 int e5 = right - sixth;
2047 int e3 = (left + right) >>> 1; // The midpoint
2048 int e4 = e3 + sixth;
2049 int e2 = e3 - sixth;
2050
2051 // Sort these elements using a 5-element sorting network
2052 double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
2053
2054 if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
2055 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
2056 if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
2057 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
2058 if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
2059 if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
2060 if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
2061 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
2062 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
2063
2064 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
2065
2066 /*
2067 * Use the second and fourth of the five sorted elements as pivots.
2068 * These values are inexpensive approximations of the first and
2069 * second terciles of the array. Note that pivot1 <= pivot2.
2070 *
2071 * The pivots are stored in local variables, and the first and
2072 * the last of the elements to be sorted are moved to the locations
2073 * formerly occupied by the pivots. When partitioning is complete,
2074 * the pivots are swapped back into their final positions, and
2075 * excluded from subsequent sorting.
2076 */
2077 double pivot1 = ae2; a[e2] = a[left];
2078 double pivot2 = ae4; a[e4] = a[right];
2079
2080 // Pointers
2081 int less = left + 1; // The index of first element of center part
2082 int great = right - 1; // The index before first element of right part
2083
2084 boolean pivotsDiffer = (pivot1 != pivot2);
2085
2086 if (pivotsDiffer) {
2087 /*
2088 * Partitioning:
2089 *
2090 * left part center part right part
2091 * +------------------------------------------------------------+
2092 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
2093 * +------------------------------------------------------------+
2094 * ^ ^ ^
2095 * | | |
2096 * less k great
2097 *
2098 * Invariants:
2099 *
2100 * all in (left, less) < pivot1
2101 * pivot1 <= all in [less, k) <= pivot2
2102 * all in (great, right) > pivot2
2103 *
2104 * Pointer k is the first index of ?-part
2105 */
2106 outer:
2107 for (int k = less; k <= great; k++) {
2108 double ak = a[k];
2109 if (ak < pivot1) { // Move a[k] to left part
2110 if (k != less) {
2111 a[k] = a[less];
2112 a[less] = ak;
2113 }
2114 less++;
2115 } else if (ak > pivot2) { // Move a[k] to right part
2116 while (a[great] > pivot2) {
2117 if (great-- == k) {
2118 break outer;
2119 }
2120 }
2121 if (a[great] < pivot1) {
2122 a[k] = a[less];
2123 a[less++] = a[great];
2124 a[great--] = ak;
2125 } else { // pivot1 <= a[great] <= pivot2
2126 a[k] = a[great];
2127 a[great--] = ak;
2128 }
2129 }
2130 }
2131 } else { // Pivots are equal
2132 /*
2133 * Partition degenerates to the traditional 3-way,
2134 * or "Dutch National Flag", partition:
2135 *
2136 * left part center part right part
2137 * +----------------------------------------------+
2138 * | < pivot | == pivot | ? | > pivot |
2139 * +----------------------------------------------+
2140 * ^ ^ ^
2141 * | | |
2142 * less k great
2143 *
2144 * Invariants:
2145 *
2146 * all in (left, less) < pivot
2147 * all in [less, k) == pivot
2148 * all in (great, right) > pivot
2149 *
2150 * Pointer k is the first index of ?-part
2151 */
2152 for (int k = less; k <= great; k++) {
2153 double ak = a[k];
2154 if (ak == pivot1) {
2155 continue;
2156 }
2157 if (ak < pivot1) { // Move a[k] to left part
2158 if (k != less) {
2159 a[k] = a[less];
2160 a[less] = ak;
2161 }
2162 less++;
2163 } else { // (a[k] > pivot1) - Move a[k] to right part
2164 /*
2165 * We know that pivot1 == a[e3] == pivot2. Thus, we know
2166 * that great will still be >= k when the following loop
2167 * terminates, even though we don't test for it explicitly.
2168 * In other words, a[e3] acts as a sentinel for great.
2169 */
2170 while (a[great] > pivot1) {
2171 great--;
2172 }
2173 if (a[great] < pivot1) {
2174 a[k] = a[less];
2175 a[less++] = a[great];
2176 a[great--] = ak;
2177 } else { // a[great] == pivot1
2178 a[k] = pivot1;
2179 a[great--] = ak;
2180 }
2181 }
2182 }
2183 }
2184
2185 // Swap pivots into their final positions
2186 a[left] = a[less - 1]; a[less - 1] = pivot1;
2187 a[right] = a[great + 1]; a[great + 1] = pivot2;
2188
2189 // Sort left and right parts recursively, excluding known pivot values
2190 doSort(a, left, less - 2);
2191 doSort(a, great + 2, right);
2192
2193 /*
2194 * If pivot1 == pivot2, all elements from center
2195 * part are equal and, therefore, already sorted
2196 */
2197 if (!pivotsDiffer) {
2198 return;
2199 }
2200
2201 /*
2202 * If center part is too large (comprises > 2/3 of the array),
2203 * swap internal pivot values to ends
2204 */
2205 if (less < e1 && great > e5) {
2206 while (a[less] == pivot1) {
2207 less++;
2208 }
2209 while (a[great] == pivot2) {
2210 great--;
2211 }
2212
2213 /*
2214 * Partitioning:
2215 *
2216 * left part center part right part
2217 * +----------------------------------------------------------+
2218 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
2219 * +----------------------------------------------------------+
2220 * ^ ^ ^
2221 * | | |
2222 * less k great
2223 *
2224 * Invariants:
2225 *
2226 * all in (*, less) == pivot1
2227 * pivot1 < all in [less, k) < pivot2
2228 * all in (great, *) == pivot2
2229 *
2230 * Pointer k is the first index of ?-part
2231 */
2232 outer:
2233 for (int k = less; k <= great; k++) {
2234 double ak = a[k];
2235 if (ak == pivot2) { // Move a[k] to right part
2236 while (a[great] == pivot2) {
2237 if (great-- == k) {
2238 break outer;
2239 }
2240 }
2241 if (a[great] == pivot1) {
2242 a[k] = a[less];
2243 a[less++] = pivot1;
2244 } else { // pivot1 < a[great] < pivot2
2245 a[k] = a[great];
2246 }
2247 a[great--] = pivot2;
2248 } else if (ak == pivot1) { // Move a[k] to left part
2249 a[k] = a[less];
2250 a[less++] = pivot1;
2251 }
2252 }
2253 }
2254
2255 // Sort center part recursively, excluding known pivot values
2256 doSort(a, less, great);
2257 }
2258
2259 /**
2260 * Checks that {@code fromIndex} and {@code toIndex} are in
2261 * the range and throws an appropriate exception, if they aren't.
2262 */
2263 private static void rangeCheck(int length, int fromIndex, int toIndex) {
2264 if (fromIndex > toIndex) {
2265 throw new IllegalArgumentException(
2266 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
2267 }
2268 if (fromIndex < 0) {
2269 throw new ArrayIndexOutOfBoundsException(fromIndex);
2270 }
2271 if (toIndex > length) {
2272 throw new ArrayIndexOutOfBoundsException(toIndex);
2273 }
2274 }
2275 }
|
1 /*
2 * Copyright 2010 Sun Microsystems, Inc. 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. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package java.util;
27
28 /**
29 * This class implements the Dual-Pivot Quicksort algorithm by
30 * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
31 * offers O(n log(n)) performance on many data sets that cause other
32 * quicksorts to degrade to quadratic performance, and is typically
33 * faster than traditional (one-pivot) Quicksort implementations.
34 *
35 * @author Vladimir Yaroslavskiy
36 * @author Jon Bentley
37 * @author Josh Bloch
38 *
39 * @version 2010.04.25 m765.827.12i:5\7
40 * @since 1.7
41 */
42 final class DualPivotQuicksort {
43
44 /**
45 * Prevents instantiation.
46 */
47 private DualPivotQuicksort() {}
48
49 /*
50 * Tuning parameters.
51 */
52
53 /**
54 * If the length of an array to be sorted is less than this
55 * constant, insertion sort is used in preference to Quicksort.
56 */
57 private static final int INSERTION_SORT_THRESHOLD = 32;
58
59 /**
60 * If the length of a byte array to be sorted is greater than
61 * this constant, counting sort is used in preference to Quicksort.
62 */
63 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
64
65 /**
66 * If the length of a short or char array to be sorted is greater
67 * than this constant, counting sort is used in preference to Quicksort.
68 */
69 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
70
71 /*
72 * Sorting methods for seven primitive types.
73 */
74
75 /**
76 * Sorts the specified array into ascending numerical order.
77 *
78 * @param a the array to be sorted
79 */
80 public static void sort(int[] a) {
81 dualPivotQuicksort(a, 0, a.length - 1);
82 }
83
84 /**
85 * Sorts the specified range of the array into ascending order. The range
86 * to be sorted extends from the index {@code fromIndex}, inclusive, to
87 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
88 * the range to be sorted is empty (and the call is a no-op).
89 *
90 * @param a the array to be sorted
91 * @param fromIndex the index of the first element, inclusive, to be sorted
92 * @param toIndex the index of the last element, exclusive, to be sorted
93 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
94 * @throws ArrayIndexOutOfBoundsException
95 * if {@code fromIndex < 0} or {@code toIndex > a.length}
96 */
97 public static void sort(int[] a, int fromIndex, int toIndex) {
98 rangeCheck(a.length, fromIndex, toIndex);
99 dualPivotQuicksort(a, fromIndex, toIndex - 1);
100 }
101
102 /**
103 * Sorts the specified range of the array into ascending order by the
104 * Dual-Pivot Quicksort algorithm.
105 *
106 * @param a the array to be sorted
107 * @param left the index of the first element, inclusive, to be sorted
108 * @param right the index of the last element, inclusive, to be sorted
109 */
110 private static void dualPivotQuicksort(int[] a, int left, int right) {
111 int length = right - left + 1;
112
113 // Skip trivial arrays
114 if (length < 2) {
115 return;
116 }
117
118 // Use insertion sort on tiny arrays
119 if (length < INSERTION_SORT_THRESHOLD) {
120 if (left > 0) {
121 /*
122 * Set minimum value as a sentinel before the specified
123 * range of the array, it allows to avoid expensive
124 * check j >= left on each iteration.
125 */
126 int before = a[left - 1]; a[left - 1] = Integer.MIN_VALUE;
127
128 for (int j, i = left + 1; i <= right; i++) {
129 int ai = a[i];
130 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
131 a[j + 1] = a[j];
132 }
133 a[j + 1] = ai;
134 }
135 a[left - 1] = before;
136 } else {
137 /*
138 * For case, when left == 0, traditional (without a sentinel)
139 * insertion sort, optimized for server VM, is used.
140 */
141 for (int i = 0, j = i; i < right; j = ++i) {
142 int ai = a[i + 1];
143 while (ai < a[j]) {
144 a[j + 1] = a[j];
145 if (j-- == 0) {
146 break;
147 }
148 }
149 a[j + 1] = ai;
150 }
151 }
152 return;
153 }
154
155 // Inexpensive approximation of one seventh
156 int seventh = (length >>> 3) + (length >>> 6) + 1;
157
158 // Compute indices of 5 center evenly spaced elements
159 int e3 = (left + right) >>> 1; // The midpoint
160 int e2 = e3 - seventh, e1 = e2 - seventh;
161 int e4 = e3 + seventh, e5 = e4 + seventh;
162
163 // Sort these elements using a 5-element sorting network
164 int ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
165
166 if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
167 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
168 if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
169 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
170 if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
171 if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
172 if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
173 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
174 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
175
176 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
177
178 /*
179 * Use the second and fourth of the five sorted elements as pivots.
180 * These values are inexpensive approximations of the first and
181 * second terciles of the array. Note that pivot1 <= pivot2.
182 */
183 int pivot1 = a[e2];
184 int pivot2 = a[e4];
185
186 // Pointers
187 int less = left; // The index of the first element of center part
188 int great = right; // The index before the first element of right part
189
190 if (pivot1 < pivot2) {
191 /*
192 * The first and the last elements to be sorted are moved to the
193 * locations formerly occupied by the pivots. When partitioning
194 * is complete, the pivots are swapped back into their final
195 * positions, and excluded from subsequent sorting.
196 */
197 a[e2] = a[less++];
198 a[e4] = a[great--];
199
200 /*
201 * Partitioning:
202 *
203 * left part center part right part
204 * +--------------------------------------------------------------+
205 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
206 * +--------------------------------------------------------------+
207 * ^ ^ ^
208 * | | |
209 * less k great
210 *
211 * Invariants:
212 *
213 * all in (left, less) < pivot1
214 * pivot1 <= all in [less, k) <= pivot2
215 * all in (great, right) > pivot2
216 *
217 * Pointer k is the first index of not inspected ?-part.
218 */
219 outer:
220 for (int k = less; k <= great; k++) {
221 int ak = a[k];
222 if (ak < pivot1) { // Move a[k] to left part
223 if (k != less) {
224 a[k] = a[less];
225 a[less] = ak;
226 }
227 less++;
228 } else if (ak > pivot2) { // Move a[k] to right part
229 while (a[great] > pivot2) {
230 if (great-- == k) {
231 break outer;
232 }
233 }
234 if (a[great] < pivot1) {
235 a[k] = a[less];
236 a[less++] = a[great];
237 } else { // pivot1 <= a[great] <= pivot2
238 a[k] = a[great];
239 }
240 a[great--] = ak;
241 }
242 }
243
244 // Swap pivots into their final positions
245 a[left] = a[less - 1]; a[less - 1] = pivot1;
246 a[right] = a[great + 1]; a[great + 1] = pivot2;
247
248 // Sort left and right parts recursively, excluding known pivots
249 dualPivotQuicksort(a, left, less - 2);
250 dualPivotQuicksort(a, great + 2, right);
251
252 /*
253 * If center part is too large (comprises > 5/7 of the array),
254 * swap internal pivot values to ends.
255 */
256 if (great - less > 5 * seventh) {
257 while (a[less] == pivot1) {
258 less++;
259 }
260 while (a[great] == pivot2) {
261 great--;
262 }
263
264 /*
265 * Partitioning:
266 *
267 * left part center part right part
268 * +----------------------------------------------------------+
269 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
270 * +----------------------------------------------------------+
271 * ^ ^ ^
272 * | | |
273 * less k great
274 *
275 * Invariants:
276 *
277 * all in (*, less) == pivot1
278 * pivot1 < all in [less, k) < pivot2
279 * all in (great, *) == pivot2
280 *
281 * Pointer k is the first index of not inspected ?-part.
282 */
283 outer:
284 for (int k = less; k <= great; k++) {
285 int ak = a[k];
286 if (ak == pivot2) { // Move a[k] to right part
287 while (a[great] == pivot2) {
288 if (great-- == k) {
289 break outer;
290 }
291 }
292 if (a[great] == pivot1) {
293 a[k] = a[less];
294 a[less++] = pivot1;
295 } else { // pivot1 < a[great] < pivot2
296 a[k] = a[great];
297 }
298 a[great--] = pivot2;
299 } else if (ak == pivot1) { // Move a[k] to left part
300 a[k] = a[less];
301 a[less++] = pivot1;
302 }
303 }
304 }
305
306 // Sort center part recursively
307 dualPivotQuicksort(a, less, great);
308
309 } else { // Pivots are equal
310 /*
311 * Partition degenerates to the traditional 3-way
312 * (or "Dutch National Flag") schema:
313 *
314 * left part center part right part
315 * +----------------------------------------------+
316 * | < pivot | == pivot | ? | > pivot |
317 * +----------------------------------------------+
318 * ^ ^ ^
319 * | | |
320 * less k great
321 *
322 * Invariants:
323 *
324 * all in (left, less) < pivot
325 * all in [less, k) == pivot
326 * all in (great, right) > pivot
327 *
328 * Pointer k is the first index of not inspected ?-part.
329 */
330 for (int k = less; k <= great; k++) {
331 int ak = a[k];
332 if (ak == pivot1) {
333 continue;
334 }
335 if (ak < pivot1) { // Move a[k] to left part
336 if (k != less) {
337 a[k] = a[less];
338 a[less] = ak;
339 }
340 less++;
341 } else { // a[k] > pivot1 - Move a[k] to right part
342 /*
343 * We know that pivot1 == a[e3] == pivot2. Thus, we know
344 * that great will still be >= k when the following loop
345 * terminates, even though we don't test for it explicitly.
346 * In other words, a[e3] acts as a sentinel for great.
347 */
348 while (a[great] > pivot1) {
349 great--;
350 }
351 if (a[great] < pivot1) {
352 a[k] = a[less];
353 a[less++] = a[great];
354 } else { // a[great] == pivot1
355 a[k] = pivot1;
356 }
357 a[great--] = ak;
358 }
359 }
360
361 // Sort left and right parts recursively
362 dualPivotQuicksort(a, left, less - 1);
363 dualPivotQuicksort(a, great + 1, right);
364 }
365 }
366
367 /**
368 * Sorts the specified array into ascending numerical order.
369 *
370 * @param a the array to be sorted
371 */
372 public static void sort(long[] a) {
373 dualPivotQuicksort(a, 0, a.length - 1);
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 (and the call is a no-op).
381 *
382 * @param a the array to be sorted
383 * @param fromIndex the index of the first element, inclusive, to be sorted
384 * @param toIndex the index of the last element, exclusive, to be sorted
385 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
386 * @throws ArrayIndexOutOfBoundsException
387 * if {@code fromIndex < 0} or {@code toIndex > a.length}
388 */
389 public static void sort(long[] a, int fromIndex, int toIndex) {
390 rangeCheck(a.length, fromIndex, toIndex);
391 dualPivotQuicksort(a, fromIndex, toIndex - 1);
392 }
393
394 /**
395 * Sorts the specified range of the array into ascending order by the
396 * Dual-Pivot Quicksort algorithm.
397 *
398 * @param a the array to be sorted
399 * @param left the index of the first element, inclusive, to be sorted
400 * @param right the index of the last element, inclusive, to be sorted
401 */
402 private static void dualPivotQuicksort(long[] a, int left, int right) {
403 int length = right - left + 1;
404
405 // Skip trivial arrays
406 if (length < 2) {
407 return;
408 }
409
410 // Use insertion sort on tiny arrays
411 if (length < INSERTION_SORT_THRESHOLD) {
412 if (left > 0) {
413 /*
414 * Set minimum value as a sentinel before the specified
415 * range of the array, it allows to avoid expensive
416 * check j >= left on each iteration.
417 */
418 long before = a[left - 1]; a[left - 1] = Long.MIN_VALUE;
419
420 for (int j, i = left + 1; i <= right; i++) {
421 long ai = a[i];
422 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
423 a[j + 1] = a[j];
424 }
425 a[j + 1] = ai;
426 }
427 a[left - 1] = before;
428 } else {
429 /*
430 * For case, when left == 0, traditional (without a sentinel)
431 * insertion sort, optimized for server VM, is used.
432 */
433 for (int i = 0, j = i; i < right; j = ++i) {
434 long ai = a[i + 1];
435 while (ai < a[j]) {
436 a[j + 1] = a[j];
437 if (j-- == 0) {
438 break;
439 }
440 }
441 a[j + 1] = ai;
442 }
443 }
444 return;
445 }
446
447 // Inexpensive approximation of one seventh
448 int seventh = (length >>> 3) + (length >>> 6) + 1;
449
450 // Compute indices of 5 center evenly spaced elements
451 int e3 = (left + right) >>> 1; // The midpoint
452 int e2 = e3 - seventh, e1 = e2 - seventh;
453 int e4 = e3 + seventh, e5 = e4 + seventh;
454
455 // Sort these elements using a 5-element sorting network
456 long ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
457
458 if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
459 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
460 if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
461 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
462 if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
463 if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
464 if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
465 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
466 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
467
468 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
469
470 /*
471 * Use the second and fourth of the five sorted elements as pivots.
472 * These values are inexpensive approximations of the first and
473 * second terciles of the array. Note that pivot1 <= pivot2.
474 */
475 long pivot1 = a[e2];
476 long pivot2 = a[e4];
477
478 // Pointers
479 int less = left; // The index of the first element of center part
480 int great = right; // The index before the first element of right part
481
482 if (pivot1 < pivot2) {
483 /*
484 * The first and the last elements to be sorted are moved to the
485 * locations formerly occupied by the pivots. When partitioning
486 * is complete, the pivots are swapped back into their final
487 * positions, and excluded from subsequent sorting.
488 */
489 a[e2] = a[less++];
490 a[e4] = a[great--];
491
492 /*
493 * Partitioning:
494 *
495 * left part center part right part
496 * +--------------------------------------------------------------+
497 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
498 * +--------------------------------------------------------------+
499 * ^ ^ ^
500 * | | |
501 * less k great
502 *
503 * Invariants:
504 *
505 * all in (left, less) < pivot1
506 * pivot1 <= all in [less, k) <= pivot2
507 * all in (great, right) > pivot2
508 *
509 * Pointer k is the first index of not inspected ?-part.
510 */
511 outer:
512 for (int k = less; k <= great; k++) {
513 long ak = a[k];
514 if (ak < pivot1) { // Move a[k] to left part
515 if (k != less) {
516 a[k] = a[less];
517 a[less] = ak;
518 }
519 less++;
520 } else if (ak > pivot2) { // Move a[k] to right part
521 while (a[great] > pivot2) {
522 if (great-- == k) {
523 break outer;
524 }
525 }
526 if (a[great] < pivot1) {
527 a[k] = a[less];
528 a[less++] = a[great];
529 } else { // pivot1 <= a[great] <= pivot2
530 a[k] = a[great];
531 }
532 a[great--] = ak;
533 }
534 }
535
536 // Swap pivots into their final positions
537 a[left] = a[less - 1]; a[less - 1] = pivot1;
538 a[right] = a[great + 1]; a[great + 1] = pivot2;
539
540 // Sort left and right parts recursively, excluding known pivots
541 dualPivotQuicksort(a, left, less - 2);
542 dualPivotQuicksort(a, great + 2, right);
543
544 /*
545 * If center part is too large (comprises > 5/7 of the array),
546 * swap internal pivot values to ends.
547 */
548 if (great - less > 5 * seventh) {
549 while (a[less] == pivot1) {
550 less++;
551 }
552 while (a[great] == pivot2) {
553 great--;
554 }
555
556 /*
557 * Partitioning:
558 *
559 * left part center part right part
560 * +----------------------------------------------------------+
561 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
562 * +----------------------------------------------------------+
563 * ^ ^ ^
564 * | | |
565 * less k great
566 *
567 * Invariants:
568 *
569 * all in (*, less) == pivot1
570 * pivot1 < all in [less, k) < pivot2
571 * all in (great, *) == pivot2
572 *
573 * Pointer k is the first index of not inspected ?-part.
574 */
575 outer:
576 for (int k = less; k <= great; k++) {
577 long ak = a[k];
578 if (ak == pivot2) { // Move a[k] to right part
579 while (a[great] == pivot2) {
580 if (great-- == k) {
581 break outer;
582 }
583 }
584 if (a[great] == pivot1) {
585 a[k] = a[less];
586 a[less++] = pivot1;
587 } else { // pivot1 < a[great] < pivot2
588 a[k] = a[great];
589 }
590 a[great--] = pivot2;
591 } else if (ak == pivot1) { // Move a[k] to left part
592 a[k] = a[less];
593 a[less++] = pivot1;
594 }
595 }
596 }
597
598 // Sort center part recursively
599 dualPivotQuicksort(a, less, great);
600
601 } else { // Pivots are equal
602 /*
603 * Partition degenerates to the traditional 3-way
604 * (or "Dutch National Flag") schema:
605 *
606 * left part center part right part
607 * +----------------------------------------------+
608 * | < pivot | == pivot | ? | > pivot |
609 * +----------------------------------------------+
610 * ^ ^ ^
611 * | | |
612 * less k great
613 *
614 * Invariants:
615 *
616 * all in (left, less) < pivot
617 * all in [less, k) == pivot
618 * all in (great, right) > pivot
619 *
620 * Pointer k is the first index of not inspected ?-part.
621 */
622 for (int k = less; k <= great; k++) {
623 long ak = a[k];
624 if (ak == pivot1) {
625 continue;
626 }
627 if (ak < pivot1) { // Move a[k] to left part
628 if (k != less) {
629 a[k] = a[less];
630 a[less] = ak;
631 }
632 less++;
633 } else { // a[k] > pivot1 - Move a[k] to right part
634 /*
635 * We know that pivot1 == a[e3] == pivot2. Thus, we know
636 * that great will still be >= k when the following loop
637 * terminates, even though we don't test for it explicitly.
638 * In other words, a[e3] acts as a sentinel for great.
639 */
640 while (a[great] > pivot1) {
641 great--;
642 }
643 if (a[great] < pivot1) {
644 a[k] = a[less];
645 a[less++] = a[great];
646 } else { // a[great] == pivot1
647 a[k] = pivot1;
648 }
649 a[great--] = ak;
650 }
651 }
652
653 // Sort left and right parts recursively
654 dualPivotQuicksort(a, left, less - 1);
655 dualPivotQuicksort(a, great + 1, right);
656 }
657 }
658
659 /**
660 * Sorts the specified array into ascending numerical order.
661 *
662 * @param a the array to be sorted
663 */
664 public static void sort(short[] a) {
665 dualPivotQuicksort(a, 0, a.length - 1);
666 }
667
668 /**
669 * Sorts the specified range of the array into ascending order. The range
670 * to be sorted extends from the index {@code fromIndex}, inclusive, to
671 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
672 * the range to be sorted is empty (and the call is a no-op).
673 *
674 * @param a the array to be sorted
675 * @param fromIndex the index of the first element, inclusive, to be sorted
676 * @param toIndex the index of the last element, exclusive, to be sorted
677 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
678 * @throws ArrayIndexOutOfBoundsException
679 * if {@code fromIndex < 0} or {@code toIndex > a.length}
680 */
681 public static void sort(short[] a, int fromIndex, int toIndex) {
682 rangeCheck(a.length, fromIndex, toIndex);
683 dualPivotQuicksort(a, fromIndex, toIndex - 1);
684 }
685
686 /** The number of distinct short values. */
687 private static final int NUM_SHORT_VALUES = 1 << 16;
688
689 /**
690 * Sorts the specified range of the array into ascending order by the
691 * Dual-Pivot Quicksort algorithm.
692 *
693 * @param a the array to be sorted
694 * @param left the index of the first element, inclusive, to be sorted
695 * @param right the index of the last element, inclusive, to be sorted
696 */
697 private static void dualPivotQuicksort(short[] a, int left, int right) {
698 int length = right - left + 1;
699
700 // Skip trivial arrays
701 if (length < 2) {
702 return;
703 }
704
705 // Use insertion sort on tiny arrays
706 if (length < INSERTION_SORT_THRESHOLD) {
707 if (left > 0) {
708 /*
709 * Set minimum value as a sentinel before the specified
710 * range of the array, it allows to avoid expensive
711 * check j >= left on each iteration.
712 */
713 short before = a[left - 1]; a[left - 1] = Short.MIN_VALUE;
714
715 for (int j, i = left + 1; i <= right; i++) {
716 short ai = a[i];
717 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
718 a[j + 1] = a[j];
719 }
720 a[j + 1] = ai;
721 }
722 a[left - 1] = before;
723 } else {
724 /*
725 * For case, when left == 0, traditional (without a sentinel)
726 * insertion sort, optimized for server VM, is used.
727 */
728 for (int i = 0, j = i; i < right; j = ++i) {
729 short ai = a[i + 1];
730 while (ai < a[j]) {
731 a[j + 1] = a[j];
732 if (j-- == 0) {
733 break;
734 }
735 }
736 a[j + 1] = ai;
737 }
738 }
739 return;
740 }
741
742 // Use counting sort on huge arrays
743 if (length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
744 int[] count = new int[NUM_SHORT_VALUES];
745
746 for (int i = left; i <= right; i++) {
747 count[a[i] - Short.MIN_VALUE]++;
748 }
749 for (int i = 0, k = left; i < count.length && k <= right; i++) {
750 short value = (short) (i + Short.MIN_VALUE);
751
752 for (int s = count[i]; s > 0; s--) {
753 a[k++] = value;
754 }
755 }
756 return;
757 }
758
759 // Inexpensive approximation of one seventh
760 int seventh = (length >>> 3) + (length >>> 6) + 1;
761
762 // Compute indices of 5 center evenly spaced elements
763 int e3 = (left + right) >>> 1; // The midpoint
764 int e2 = e3 - seventh, e1 = e2 - seventh;
765 int e4 = e3 + seventh, e5 = e4 + seventh;
766
767 // Sort these elements using a 5-element sorting network
768 short ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
769
770 if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
771 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
772 if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
773 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
774 if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
775 if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
776 if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
777 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
778 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
779
780 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
781
782 /*
783 * Use the second and fourth of the five sorted elements as pivots.
784 * These values are inexpensive approximations of the first and
785 * second terciles of the array. Note that pivot1 <= pivot2.
786 */
787 short pivot1 = a[e2];
788 short pivot2 = a[e4];
789
790 // Pointers
791 int less = left; // The index of the first element of center part
792 int great = right; // The index before the first element of right part
793
794 if (pivot1 < pivot2) {
795 /*
796 * The first and the last elements to be sorted are moved to the
797 * locations formerly occupied by the pivots. When partitioning
798 * is complete, the pivots are swapped back into their final
799 * positions, and excluded from subsequent sorting.
800 */
801 a[e2] = a[less++];
802 a[e4] = a[great--];
803
804 /*
805 * Partitioning:
806 *
807 * left part center part right part
808 * +--------------------------------------------------------------+
809 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
810 * +--------------------------------------------------------------+
811 * ^ ^ ^
812 * | | |
813 * less k great
814 *
815 * Invariants:
816 *
817 * all in (left, less) < pivot1
818 * pivot1 <= all in [less, k) <= pivot2
819 * all in (great, right) > pivot2
820 *
821 * Pointer k is the first index of not inspected ?-part.
822 */
823 outer:
824 for (int k = less; k <= great; k++) {
825 short ak = a[k];
826 if (ak < pivot1) { // Move a[k] to left part
827 if (k != less) {
828 a[k] = a[less];
829 a[less] = ak;
830 }
831 less++;
832 } else if (ak > pivot2) { // Move a[k] to right part
833 while (a[great] > pivot2) {
834 if (great-- == k) {
835 break outer;
836 }
837 }
838 if (a[great] < pivot1) {
839 a[k] = a[less];
840 a[less++] = a[great];
841 } else { // pivot1 <= a[great] <= pivot2
842 a[k] = a[great];
843 }
844 a[great--] = ak;
845 }
846 }
847
848 // Swap pivots into their final positions
849 a[left] = a[less - 1]; a[less - 1] = pivot1;
850 a[right] = a[great + 1]; a[great + 1] = pivot2;
851
852 // Sort left and right parts recursively, excluding known pivots
853 dualPivotQuicksort(a, left, less - 2);
854 dualPivotQuicksort(a, great + 2, right);
855
856 /*
857 * If center part is too large (comprises > 5/7 of the array),
858 * swap internal pivot values to ends.
859 */
860 if (great - less > 5 * seventh) {
861 while (a[less] == pivot1) {
862 less++;
863 }
864 while (a[great] == pivot2) {
865 great--;
866 }
867
868 /*
869 * Partitioning:
870 *
871 * left part center part right part
872 * +----------------------------------------------------------+
873 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
874 * +----------------------------------------------------------+
875 * ^ ^ ^
876 * | | |
877 * less k great
878 *
879 * Invariants:
880 *
881 * all in (*, less) == pivot1
882 * pivot1 < all in [less, k) < pivot2
883 * all in (great, *) == pivot2
884 *
885 * Pointer k is the first index of not inspected ?-part.
886 */
887 outer:
888 for (int k = less; k <= great; k++) {
889 short ak = a[k];
890 if (ak == pivot2) { // Move a[k] to right part
891 while (a[great] == pivot2) {
892 if (great-- == k) {
893 break outer;
894 }
895 }
896 if (a[great] == pivot1) {
897 a[k] = a[less];
898 a[less++] = pivot1;
899 } else { // pivot1 < a[great] < pivot2
900 a[k] = a[great];
901 }
902 a[great--] = pivot2;
903 } else if (ak == pivot1) { // Move a[k] to left part
904 a[k] = a[less];
905 a[less++] = pivot1;
906 }
907 }
908 }
909
910 // Sort center part recursively
911 dualPivotQuicksort(a, less, great);
912
913 } else { // Pivots are equal
914 /*
915 * Partition degenerates to the traditional 3-way
916 * (or "Dutch National Flag") schema:
917 *
918 * left part center part right part
919 * +----------------------------------------------+
920 * | < pivot | == pivot | ? | > pivot |
921 * +----------------------------------------------+
922 * ^ ^ ^
923 * | | |
924 * less k great
925 *
926 * Invariants:
927 *
928 * all in (left, less) < pivot
929 * all in [less, k) == pivot
930 * all in (great, right) > pivot
931 *
932 * Pointer k is the first index of not inspected ?-part.
933 */
934 for (int k = less; k <= great; k++) {
935 short ak = a[k];
936 if (ak == pivot1) {
937 continue;
938 }
939 if (ak < pivot1) { // Move a[k] to left part
940 if (k != less) {
941 a[k] = a[less];
942 a[less] = ak;
943 }
944 less++;
945 } else { // a[k] > pivot1 - Move a[k] to right part
946 /*
947 * We know that pivot1 == a[e3] == pivot2. Thus, we know
948 * that great will still be >= k when the following loop
949 * terminates, even though we don't test for it explicitly.
950 * In other words, a[e3] acts as a sentinel for great.
951 */
952 while (a[great] > pivot1) {
953 great--;
954 }
955 if (a[great] < pivot1) {
956 a[k] = a[less];
957 a[less++] = a[great];
958 } else { // a[great] == pivot1
959 a[k] = pivot1;
960 }
961 a[great--] = ak;
962 }
963 }
964
965 // Sort left and right parts recursively
966 dualPivotQuicksort(a, left, less - 1);
967 dualPivotQuicksort(a, great + 1, right);
968 }
969 }
970
971 /**
972 * Sorts the specified array into ascending numerical order.
973 *
974 * @param a the array to be sorted
975 */
976 public static void sort(char[] a) {
977 dualPivotQuicksort(a, 0, a.length - 1);
978 }
979
980 /**
981 * Sorts the specified range of the array into ascending order. The range
982 * to be sorted extends from the index {@code fromIndex}, inclusive, to
983 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
984 * the range to be sorted is empty (and the call is a no-op).
985 *
986 * @param a the array to be sorted
987 * @param fromIndex the index of the first element, inclusive, to be sorted
988 * @param toIndex the index of the last element, exclusive, to be sorted
989 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
990 * @throws ArrayIndexOutOfBoundsException
991 * if {@code fromIndex < 0} or {@code toIndex > a.length}
992 */
993 public static void sort(char[] a, int fromIndex, int toIndex) {
994 rangeCheck(a.length, fromIndex, toIndex);
995 dualPivotQuicksort(a, fromIndex, toIndex - 1);
996 }
997
998 /** The number of distinct char values. */
999 private static final int NUM_CHAR_VALUES = 1 << 16;
1000
1001 /**
1002 * Sorts the specified range of the array into ascending order by the
1003 * Dual-Pivot Quicksort algorithm.
1004 *
1005 * @param a the array to be sorted
1006 * @param left the index of the first element, inclusive, to be sorted
1007 * @param right the index of the last element, inclusive, to be sorted
1008 */
1009 private static void dualPivotQuicksort(char[] a, int left, int right) {
1010 int length = right - left + 1;
1011
1012 // Skip trivial arrays
1013 if (length < 2) {
1014 return;
1015 }
1016
1017 // Use insertion sort on tiny arrays
1018 if (length < INSERTION_SORT_THRESHOLD) {
1019 if (left > 0) {
1020 /*
1021 * Set minimum value as a sentinel before the specified
1022 * range of the array, it allows to avoid expensive
1023 * check j >= left on each iteration.
1024 */
1025 char before = a[left - 1]; a[left - 1] = Character.MIN_VALUE;
1026
1027 for (int j, i = left + 1; i <= right; i++) {
1028 char ai = a[i];
1029 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
1030 a[j + 1] = a[j];
1031 }
1032 a[j + 1] = ai;
1033 }
1034 a[left - 1] = before;
1035 } else {
1036 /*
1037 * For case, when left == 0, traditional (without a sentinel)
1038 * insertion sort, optimized for server VM, is used.
1039 */
1040 for (int i = 0, j = i; i < right; j = ++i) {
1041 char ai = a[i + 1];
1042 while (ai < a[j]) {
1043 a[j + 1] = a[j];
1044 if (j-- == 0) {
1045 break;
1046 }
1047 }
1048 a[j + 1] = ai;
1049 }
1050 }
1051 return;
1052 }
1053
1054 // Use counting sort on huge arrays
1055 if (length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
1056 int[] count = new int[NUM_CHAR_VALUES];
1057
1058 for (int i = left; i <= right; i++) {
1059 count[a[i]]++;
1060 }
1061 for (int i = 0, k = left; i < count.length && k <= right; i++) {
1062 for (int s = count[i]; s > 0; s--) {
1063 a[k++] = (char) i;
1064 }
1065 }
1066 return;
1067 }
1068
1069 // Inexpensive approximation of one seventh
1070 int seventh = (length >>> 3) + (length >>> 6) + 1;
1071
1072 // Compute indices of 5 center evenly spaced elements
1073 int e3 = (left + right) >>> 1; // The midpoint
1074 int e2 = e3 - seventh, e1 = e2 - seventh;
1075 int e4 = e3 + seventh, e5 = e4 + seventh;
1076
1077 // Sort these elements using a 5-element sorting network
1078 char ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
1079
1080 if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
1081 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
1082 if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
1083 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
1084 if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
1085 if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
1086 if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
1087 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
1088 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
1089
1090 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
1091
1092 /*
1093 * Use the second and fourth of the five sorted elements as pivots.
1094 * These values are inexpensive approximations of the first and
1095 * second terciles of the array. Note that pivot1 <= pivot2.
1096 */
1097 char pivot1 = a[e2];
1098 char pivot2 = a[e4];
1099
1100 // Pointers
1101 int less = left; // The index of the first element of center part
1102 int great = right; // The index before the first element of right part
1103
1104 if (pivot1 < pivot2) {
1105 /*
1106 * The first and the last elements to be sorted are moved to the
1107 * locations formerly occupied by the pivots. When partitioning
1108 * is complete, the pivots are swapped back into their final
1109 * positions, and excluded from subsequent sorting.
1110 */
1111 a[e2] = a[less++];
1112 a[e4] = a[great--];
1113
1114 /*
1115 * Partitioning:
1116 *
1117 * left part center part right part
1118 * +--------------------------------------------------------------+
1119 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1120 * +--------------------------------------------------------------+
1121 * ^ ^ ^
1122 * | | |
1123 * less k great
1124 *
1125 * Invariants:
1126 *
1127 * all in (left, less) < pivot1
1128 * pivot1 <= all in [less, k) <= pivot2
1129 * all in (great, right) > pivot2
1130 *
1131 * Pointer k is the first index of not inspected ?-part.
1132 */
1133 outer:
1134 for (int k = less; k <= great; k++) {
1135 char ak = a[k];
1136 if (ak < pivot1) { // Move a[k] to left part
1137 if (k != less) {
1138 a[k] = a[less];
1139 a[less] = ak;
1140 }
1141 less++;
1142 } else if (ak > pivot2) { // Move a[k] to right part
1143 while (a[great] > pivot2) {
1144 if (great-- == k) {
1145 break outer;
1146 }
1147 }
1148 if (a[great] < pivot1) {
1149 a[k] = a[less];
1150 a[less++] = a[great];
1151 } else { // pivot1 <= a[great] <= pivot2
1152 a[k] = a[great];
1153 }
1154 a[great--] = ak;
1155 }
1156 }
1157
1158 // Swap pivots into their final positions
1159 a[left] = a[less - 1]; a[less - 1] = pivot1;
1160 a[right] = a[great + 1]; a[great + 1] = pivot2;
1161
1162 // Sort left and right parts recursively, excluding known pivots
1163 dualPivotQuicksort(a, left, less - 2);
1164 dualPivotQuicksort(a, great + 2, right);
1165
1166 /*
1167 * If center part is too large (comprises > 5/7 of the array),
1168 * swap internal pivot values to ends.
1169 */
1170 if (great - less > 5 * seventh) {
1171 while (a[less] == pivot1) {
1172 less++;
1173 }
1174 while (a[great] == pivot2) {
1175 great--;
1176 }
1177
1178 /*
1179 * Partitioning:
1180 *
1181 * left part center part right part
1182 * +----------------------------------------------------------+
1183 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1184 * +----------------------------------------------------------+
1185 * ^ ^ ^
1186 * | | |
1187 * less k great
1188 *
1189 * Invariants:
1190 *
1191 * all in (*, less) == pivot1
1192 * pivot1 < all in [less, k) < pivot2
1193 * all in (great, *) == pivot2
1194 *
1195 * Pointer k is the first index of not inspected ?-part.
1196 */
1197 outer:
1198 for (int k = less; k <= great; k++) {
1199 char ak = a[k];
1200 if (ak == pivot2) { // Move a[k] to right part
1201 while (a[great] == pivot2) {
1202 if (great-- == k) {
1203 break outer;
1204 }
1205 }
1206 if (a[great] == pivot1) {
1207 a[k] = a[less];
1208 a[less++] = pivot1;
1209 } else { // pivot1 < a[great] < pivot2
1210 a[k] = a[great];
1211 }
1212 a[great--] = pivot2;
1213 } else if (ak == pivot1) { // Move a[k] to left part
1214 a[k] = a[less];
1215 a[less++] = pivot1;
1216 }
1217 }
1218 }
1219
1220 // Sort center part recursively
1221 dualPivotQuicksort(a, less, great);
1222
1223 } else { // Pivots are equal
1224 /*
1225 * Partition degenerates to the traditional 3-way
1226 * (or "Dutch National Flag") schema:
1227 *
1228 * left part center part right part
1229 * +----------------------------------------------+
1230 * | < pivot | == pivot | ? | > pivot |
1231 * +----------------------------------------------+
1232 * ^ ^ ^
1233 * | | |
1234 * less k great
1235 *
1236 * Invariants:
1237 *
1238 * all in (left, less) < pivot
1239 * all in [less, k) == pivot
1240 * all in (great, right) > pivot
1241 *
1242 * Pointer k is the first index of not inspected ?-part.
1243 */
1244 for (int k = less; k <= great; k++) {
1245 char ak = a[k];
1246 if (ak == pivot1) {
1247 continue;
1248 }
1249 if (ak < pivot1) { // Move a[k] to left part
1250 if (k != less) {
1251 a[k] = a[less];
1252 a[less] = ak;
1253 }
1254 less++;
1255 } else { // a[k] > pivot1 - Move a[k] to right part
1256 /*
1257 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1258 * that great will still be >= k when the following loop
1259 * terminates, even though we don't test for it explicitly.
1260 * In other words, a[e3] acts as a sentinel for great.
1261 */
1262 while (a[great] > pivot1) {
1263 great--;
1264 }
1265 if (a[great] < pivot1) {
1266 a[k] = a[less];
1267 a[less++] = a[great];
1268 } else { // a[great] == pivot1
1269 a[k] = pivot1;
1270 }
1271 a[great--] = ak;
1272 }
1273 }
1274
1275 // Sort left and right parts recursively
1276 dualPivotQuicksort(a, left, less - 1);
1277 dualPivotQuicksort(a, great + 1, right);
1278 }
1279 }
1280
1281 /**
1282 * Sorts the specified array into ascending numerical order.
1283 *
1284 * @param a the array to be sorted
1285 */
1286 public static void sort(byte[] a) {
1287 dualPivotQuicksort(a, 0, a.length - 1);
1288 }
1289
1290 /**
1291 * Sorts the specified range of the array into ascending order. The range
1292 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1293 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1294 * the range to be sorted is empty (and the call is a no-op).
1295 *
1296 * @param a the array to be sorted
1297 * @param fromIndex the index of the first element, inclusive, to be sorted
1298 * @param toIndex the index of the last element, exclusive, to be sorted
1299 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1300 * @throws ArrayIndexOutOfBoundsException
1301 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1302 */
1303 public static void sort(byte[] a, int fromIndex, int toIndex) {
1304 rangeCheck(a.length, fromIndex, toIndex);
1305 dualPivotQuicksort(a, fromIndex, toIndex - 1);
1306 }
1307
1308 /** The number of distinct byte values. */
1309 private static final int NUM_BYTE_VALUES = 1 << 8;
1310
1311 /**
1312 * Sorts the specified range of the array into ascending order by the
1313 * Dual-Pivot Quicksort algorithm.
1314 *
1315 * @param a the array to be sorted
1316 * @param left the index of the first element, inclusive, to be sorted
1317 * @param right the index of the last element, inclusive, to be sorted
1318 */
1319 private static void dualPivotQuicksort(byte[] a, int left, int right) {
1320 int length = right - left + 1;
1321
1322 // Skip trivial arrays
1323 if (length < 2) {
1324 return;
1325 }
1326
1327 // Use insertion sort on tiny arrays
1328 if (length < INSERTION_SORT_THRESHOLD) {
1329 if (left > 0) {
1330 /*
1331 * Set minimum value as a sentinel before the specified
1332 * range of the array, it allows to avoid expensive
1333 * check j >= left on each iteration.
1334 */
1335 byte before = a[left - 1]; a[left - 1] = Byte.MIN_VALUE;
1336
1337 for (int j, i = left + 1; i <= right; i++) {
1338 byte ai = a[i];
1339 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
1340 a[j + 1] = a[j];
1341 }
1342 a[j + 1] = ai;
1343 }
1344 a[left - 1] = before;
1345 } else {
1346 /*
1347 * For case, when left == 0, traditional (without a sentinel)
1348 * insertion sort, optimized for server VM, is used.
1349 */
1350 for (int i = 0, j = i; i < right; j = ++i) {
1351 byte ai = a[i + 1];
1352 while (ai < a[j]) {
1353 a[j + 1] = a[j];
1354 if (j-- == 0) {
1355 break;
1356 }
1357 }
1358 a[j + 1] = ai;
1359 }
1360 }
1361 return;
1362 }
1363
1364 // Use counting sort on huge arrays
1365 if (length > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
1366 int[] count = new int[NUM_BYTE_VALUES];
1367
1368 for (int i = left; i <= right; i++) {
1369 count[a[i] - Byte.MIN_VALUE]++;
1370 }
1371 for (int i = 0, k = left; i < count.length && k <= right; i++) {
1372 byte value = (byte) (i + Byte.MIN_VALUE);
1373
1374 for (int s = count[i]; s > 0; s--) {
1375 a[k++] = value;
1376 }
1377 }
1378 return;
1379 }
1380
1381 // Inexpensive approximation of one seventh
1382 int seventh = (length >>> 3) + (length >>> 6) + 1;
1383
1384 // Compute indices of 5 center evenly spaced elements
1385 int e3 = (left + right) >>> 1; // The midpoint
1386 int e2 = e3 - seventh, e1 = e2 - seventh;
1387 int e4 = e3 + seventh, e5 = e4 + seventh;
1388
1389 // Sort these elements using a 5-element sorting network
1390 byte ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
1391
1392 if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
1393 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1394 if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
1395 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1396 if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
1397 if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
1398 if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
1399 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1400 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1401
1402 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
1403
1404 /*
1405 * Use the second and fourth of the five sorted elements as pivots.
1406 * These values are inexpensive approximations of the first and
1407 * second terciles of the array. Note that pivot1 <= pivot2.
1408 */
1409 byte pivot1 = a[e2];
1410 byte pivot2 = a[e4];
1411
1412 // Pointers
1413 int less = left; // The index of the first element of center part
1414 int great = right; // The index before the first element of right part
1415
1416 if (pivot1 < pivot2) {
1417 /*
1418 * The first and the last elements to be sorted are moved to the
1419 * locations formerly occupied by the pivots. When partitioning
1420 * is complete, the pivots are swapped back into their final
1421 * positions, and excluded from subsequent sorting.
1422 */
1423 a[e2] = a[less++];
1424 a[e4] = a[great--];
1425
1426 /*
1427 * Partitioning:
1428 *
1429 * left part center part right part
1430 * +--------------------------------------------------------------+
1431 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1432 * +--------------------------------------------------------------+
1433 * ^ ^ ^
1434 * | | |
1435 * less k great
1436 *
1437 * Invariants:
1438 *
1439 * all in (left, less) < pivot1
1440 * pivot1 <= all in [less, k) <= pivot2
1441 * all in (great, right) > pivot2
1442 *
1443 * Pointer k is the first index of not inspected ?-part.
1444 */
1445 outer:
1446 for (int k = less; k <= great; k++) {
1447 byte ak = a[k];
1448 if (ak < pivot1) { // Move a[k] to left part
1449 if (k != less) {
1450 a[k] = a[less];
1451 a[less] = ak;
1452 }
1453 less++;
1454 } else if (ak > pivot2) { // Move a[k] to right part
1455 while (a[great] > pivot2) {
1456 if (great-- == k) {
1457 break outer;
1458 }
1459 }
1460 if (a[great] < pivot1) {
1461 a[k] = a[less];
1462 a[less++] = a[great];
1463 } else { // pivot1 <= a[great] <= pivot2
1464 a[k] = a[great];
1465 }
1466 a[great--] = ak;
1467 }
1468 }
1469
1470 // Swap pivots into their final positions
1471 a[left] = a[less - 1]; a[less - 1] = pivot1;
1472 a[right] = a[great + 1]; a[great + 1] = pivot2;
1473
1474 // Sort left and right parts recursively, excluding known pivots
1475 dualPivotQuicksort(a, left, less - 2);
1476 dualPivotQuicksort(a, great + 2, right);
1477
1478 /*
1479 * If center part is too large (comprises > 5/7 of the array),
1480 * swap internal pivot values to ends.
1481 */
1482 if (great - less > 5 * seventh) {
1483 while (a[less] == pivot1) {
1484 less++;
1485 }
1486 while (a[great] == pivot2) {
1487 great--;
1488 }
1489
1490 /*
1491 * Partitioning:
1492 *
1493 * left part center part right part
1494 * +----------------------------------------------------------+
1495 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1496 * +----------------------------------------------------------+
1497 * ^ ^ ^
1498 * | | |
1499 * less k great
1500 *
1501 * Invariants:
1502 *
1503 * all in (*, less) == pivot1
1504 * pivot1 < all in [less, k) < pivot2
1505 * all in (great, *) == pivot2
1506 *
1507 * Pointer k is the first index of not inspected ?-part.
1508 */
1509 outer:
1510 for (int k = less; k <= great; k++) {
1511 byte ak = a[k];
1512 if (ak == pivot2) { // Move a[k] to right part
1513 while (a[great] == pivot2) {
1514 if (great-- == k) {
1515 break outer;
1516 }
1517 }
1518 if (a[great] == pivot1) {
1519 a[k] = a[less];
1520 a[less++] = pivot1;
1521 } else { // pivot1 < a[great] < pivot2
1522 a[k] = a[great];
1523 }
1524 a[great--] = pivot2;
1525 } else if (ak == pivot1) { // Move a[k] to left part
1526 a[k] = a[less];
1527 a[less++] = pivot1;
1528 }
1529 }
1530 }
1531
1532 // Sort center part recursively
1533 dualPivotQuicksort(a, less, great);
1534
1535 } else { // Pivots are equal
1536 /*
1537 * Partition degenerates to the traditional 3-way
1538 * (or "Dutch National Flag") schema:
1539 *
1540 * left part center part right part
1541 * +----------------------------------------------+
1542 * | < pivot | == pivot | ? | > pivot |
1543 * +----------------------------------------------+
1544 * ^ ^ ^
1545 * | | |
1546 * less k great
1547 *
1548 * Invariants:
1549 *
1550 * all in (left, less) < pivot
1551 * all in [less, k) == pivot
1552 * all in (great, right) > pivot
1553 *
1554 * Pointer k is the first index of not inspected ?-part.
1555 */
1556 for (int k = less; k <= great; k++) {
1557 byte ak = a[k];
1558 if (ak == pivot1) {
1559 continue;
1560 }
1561 if (ak < pivot1) { // Move a[k] to left part
1562 if (k != less) {
1563 a[k] = a[less];
1564 a[less] = ak;
1565 }
1566 less++;
1567 } else { // a[k] > pivot1 - Move a[k] to right part
1568 /*
1569 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1570 * that great will still be >= k when the following loop
1571 * terminates, even though we don't test for it explicitly.
1572 * In other words, a[e3] acts as a sentinel for great.
1573 */
1574 while (a[great] > pivot1) {
1575 great--;
1576 }
1577 if (a[great] < pivot1) {
1578 a[k] = a[less];
1579 a[less++] = a[great];
1580 } else { // a[great] == pivot1
1581 a[k] = pivot1;
1582 }
1583 a[great--] = ak;
1584 }
1585 }
1586
1587 // Sort left and right parts recursively
1588 dualPivotQuicksort(a, left, less - 1);
1589 dualPivotQuicksort(a, great + 1, right);
1590 }
1591 }
1592
1593 /**
1594 * Sorts the specified array into ascending numerical order.
1595 *
1596 * <p>The {@code <} relation does not provide a total order on all float
1597 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1598 * value compares neither less than, greater than, nor equal to any value,
1599 * even itself. This method uses the total order imposed by the method
1600 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1601 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1602 * other value and all {@code Float.NaN} values are considered equal.
1603 *
1604 * @param a the array to be sorted
1605 */
1606 public static void sort(float[] a) {
1607 sortNegZeroAndNaN(a, 0, a.length - 1);
1608 }
1609
1610 /**
1611 * Sorts the specified range of the array into ascending order. The range
1612 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1613 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1614 * the range to be sorted is empty (and the call is a no-op).
1615 *
1616 * <p>The {@code <} relation does not provide a total order on all float
1617 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1618 * value compares neither less than, greater than, nor equal to any value,
1619 * even itself. This method uses the total order imposed by the method
1620 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1621 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1622 * other value and all {@code Float.NaN} values are considered equal.
1623 *
1624 * @param a the array to be sorted
1625 * @param fromIndex the index of the first element, inclusive, to be sorted
1626 * @param toIndex the index of the last element, exclusive, to be sorted
1627 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1628 * @throws ArrayIndexOutOfBoundsException
1629 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1630 */
1631 public static void sort(float[] a, int fromIndex, int toIndex) {
1632 rangeCheck(a.length, fromIndex, toIndex);
1633 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
1634 }
1635
1636 /**
1637 * Sorts the specified range of the array into ascending order. The
1638 * sort is done in three phases to avoid expensive comparisons in the
1639 * inner loop. The comparisons would be expensive due to anomalies
1640 * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
1641 *
1642 * @param a the array to be sorted
1643 * @param left the index of the first element, inclusive, to be sorted
1644 * @param right the index of the last element, inclusive, to be sorted
1645 */
1646 private static void sortNegZeroAndNaN(float[] a, int left, int right) {
1647 /*
1648 * Phase 1: Count negative zeros and move NaNs to end of array.
1649 */
1650 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
1651 int numNegativeZeros = 0;
1652 int n = right;
1653
1654 for (int k = left; k <= n; k++) {
1655 float ak = a[k];
1656 if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
1657 a[k] = 0.0f;
1658 numNegativeZeros++;
1659 } else if (ak != ak) { // i.e., ak is NaN
1660 a[k--] = a[n];
1661 a[n--] = Float.NaN;
1662 }
1663 }
1664
1665 /*
1666 * Phase 2: Sort everything except NaNs (which are already in place).
1667 */
1668 dualPivotQuicksort(a, left, n);
1669
1670 /*
1671 * Phase 3: Turn positive zeros back into negative zeros.
1672 */
1673 if (numNegativeZeros == 0) {
1674 return;
1675 }
1676
1677 // Find first zero element
1678 int zeroIndex = findAnyZero(a, left, n);
1679
1680 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
1681 zeroIndex = i;
1682 }
1683
1684 // Turn the right number of positive zeros back into negative zeros
1685 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
1686 a[i] = -0.0f;
1687 }
1688 }
1689
1690 /**
1691 * Returns the index of some zero element in the specified range via
1695 * @param a the array to be searched
1696 * @param low the index of the first element, inclusive, to be searched
1697 * @param high the index of the last element, inclusive, to be searched
1698 */
1699 private static int findAnyZero(float[] a, int low, int high) {
1700 while (true) {
1701 int middle = (low + high) >>> 1;
1702 float middleValue = a[middle];
1703
1704 if (middleValue < 0.0f) {
1705 low = middle + 1;
1706 } else if (middleValue > 0.0f) {
1707 high = middle - 1;
1708 } else { // middleValue == 0.0f
1709 return middle;
1710 }
1711 }
1712 }
1713
1714 /**
1715 * Sorts the specified range of the array into ascending order by the
1716 * Dual-Pivot Quicksort algorithm.
1717 *
1718 * @param a the array to be sorted
1719 * @param left the index of the first element, inclusive, to be sorted
1720 * @param right the index of the last element, inclusive, to be sorted
1721 */
1722 private static void dualPivotQuicksort(float[] a, int left, int right) {
1723 int length = right - left + 1;
1724
1725 // Skip trivial arrays
1726 if (length < 2) {
1727 return;
1728 }
1729
1730 // Use insertion sort on tiny arrays
1731 if (length < INSERTION_SORT_THRESHOLD) {
1732 if (left > 0) {
1733 /*
1734 * Set negative infinity as a sentinel before the specified
1735 * range of the array, it allows to avoid expensive
1736 * check j >= left on each iteration.
1737 */
1738 float before = a[left-1]; a[left-1] = Float.NEGATIVE_INFINITY;
1739
1740 for (int j, i = left + 1; i <= right; i++) {
1741 float ai = a[i];
1742 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
1743 a[j + 1] = a[j];
1744 }
1745 a[j + 1] = ai;
1746 }
1747 a[left - 1] = before;
1748 } else {
1749 /*
1750 * For case, when left == 0, traditional (without a sentinel)
1751 * insertion sort, optimized for server VM, is used.
1752 */
1753 for (int i = 0, j = i; i < right; j = ++i) {
1754 float ai = a[i + 1];
1755 while (ai < a[j]) {
1756 a[j + 1] = a[j];
1757 if (j-- == 0) {
1758 break;
1759 }
1760 }
1761 a[j + 1] = ai;
1762 }
1763 }
1764 return;
1765 }
1766
1767 // Inexpensive approximation of one seventh
1768 int seventh = (length >>> 3) + (length >>> 6) + 1;
1769
1770 // Compute indices of 5 center evenly spaced elements
1771 int e3 = (left + right) >>> 1; // The midpoint
1772 int e2 = e3 - seventh, e1 = e2 - seventh;
1773 int e4 = e3 + seventh, e5 = e4 + seventh;
1774
1775 // Sort these elements using a 5-element sorting network
1776 float ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
1777
1778 if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
1779 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1780 if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
1781 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1782 if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
1783 if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
1784 if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
1785 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1786 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1787
1788 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
1789
1790 /*
1791 * Use the second and fourth of the five sorted elements as pivots.
1792 * These values are inexpensive approximations of the first and
1793 * second terciles of the array. Note that pivot1 <= pivot2.
1794 */
1795 float pivot1 = a[e2];
1796 float pivot2 = a[e4];
1797
1798 // Pointers
1799 int less = left; // The index of the first element of center part
1800 int great = right; // The index before the first element of right part
1801
1802 if (pivot1 < pivot2) {
1803 /*
1804 * The first and the last elements to be sorted are moved to the
1805 * locations formerly occupied by the pivots. When partitioning
1806 * is complete, the pivots are swapped back into their final
1807 * positions, and excluded from subsequent sorting.
1808 */
1809 a[e2] = a[less++];
1810 a[e4] = a[great--];
1811
1812 /*
1813 * Partitioning:
1814 *
1815 * left part center part right part
1816 * +--------------------------------------------------------------+
1817 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1818 * +--------------------------------------------------------------+
1819 * ^ ^ ^
1820 * | | |
1821 * less k great
1822 *
1823 * Invariants:
1824 *
1825 * all in (left, less) < pivot1
1826 * pivot1 <= all in [less, k) <= pivot2
1827 * all in (great, right) > pivot2
1828 *
1829 * Pointer k is the first index of not inspected ?-part.
1830 */
1831 outer:
1832 for (int k = less; k <= great; k++) {
1833 float ak = a[k];
1834 if (ak < pivot1) { // Move a[k] to left part
1835 if (k != less) {
1836 a[k] = a[less];
1837 a[less] = ak;
1838 }
1839 less++;
1840 } else if (ak > pivot2) { // Move a[k] to right part
1841 while (a[great] > pivot2) {
1842 if (great-- == k) {
1843 break outer;
1844 }
1845 }
1846 if (a[great] < pivot1) {
1847 a[k] = a[less];
1848 a[less++] = a[great];
1849 } else { // pivot1 <= a[great] <= pivot2
1850 a[k] = a[great];
1851 }
1852 a[great--] = ak;
1853 }
1854 }
1855
1856 // Swap pivots into their final positions
1857 a[left] = a[less - 1]; a[less - 1] = pivot1;
1858 a[right] = a[great + 1]; a[great + 1] = pivot2;
1859
1860 // Sort left and right parts recursively, excluding known pivots
1861 dualPivotQuicksort(a, left, less - 2);
1862 dualPivotQuicksort(a, great + 2, right);
1863
1864 /*
1865 * If center part is too large (comprises > 5/7 of the array),
1866 * swap internal pivot values to ends.
1867 */
1868 if (great - less > 5 * seventh) {
1869 while (a[less] == pivot1) {
1870 less++;
1871 }
1872 while (a[great] == pivot2) {
1873 great--;
1874 }
1875
1876 /*
1877 * Partitioning:
1878 *
1879 * left part center part right part
1880 * +----------------------------------------------------------+
1881 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1882 * +----------------------------------------------------------+
1883 * ^ ^ ^
1884 * | | |
1885 * less k great
1886 *
1887 * Invariants:
1888 *
1889 * all in (*, less) == pivot1
1890 * pivot1 < all in [less, k) < pivot2
1891 * all in (great, *) == pivot2
1892 *
1893 * Pointer k is the first index of not inspected ?-part.
1894 */
1895 outer:
1896 for (int k = less; k <= great; k++) {
1897 float ak = a[k];
1898 if (ak == pivot2) { // Move a[k] to right part
1899 while (a[great] == pivot2) {
1900 if (great-- == k) {
1901 break outer;
1902 }
1903 }
1904 if (a[great] == pivot1) {
1905 a[k] = a[less];
1906 a[less++] = pivot1;
1907 } else { // pivot1 < a[great] < pivot2
1908 a[k] = a[great];
1909 }
1910 a[great--] = pivot2;
1911 } else if (ak == pivot1) { // Move a[k] to left part
1912 a[k] = a[less];
1913 a[less++] = pivot1;
1914 }
1915 }
1916 }
1917
1918 // Sort center part recursively
1919 dualPivotQuicksort(a, less, great);
1920
1921 } else { // Pivots are equal
1922 /*
1923 * Partition degenerates to the traditional 3-way
1924 * (or "Dutch National Flag") schema:
1925 *
1926 * left part center part right part
1927 * +----------------------------------------------+
1928 * | < pivot | == pivot | ? | > pivot |
1929 * +----------------------------------------------+
1930 * ^ ^ ^
1931 * | | |
1932 * less k great
1933 *
1934 * Invariants:
1935 *
1936 * all in (left, less) < pivot
1937 * all in [less, k) == pivot
1938 * all in (great, right) > pivot
1939 *
1940 * Pointer k is the first index of not inspected ?-part.
1941 */
1942 for (int k = less; k <= great; k++) {
1943 float ak = a[k];
1944 if (ak == pivot1) {
1945 continue;
1946 }
1947 if (ak < pivot1) { // Move a[k] to left part
1948 if (k != less) {
1949 a[k] = a[less];
1950 a[less] = ak;
1951 }
1952 less++;
1953 } else { // a[k] > pivot1 - Move a[k] to right part
1954 /*
1955 * We know that pivot1 == a[e3] == pivot2. Thus, we know
1956 * that great will still be >= k when the following loop
1957 * terminates, even though we don't test for it explicitly.
1958 * In other words, a[e3] acts as a sentinel for great.
1959 */
1960 while (a[great] > pivot1) {
1961 great--;
1962 }
1963 if (a[great] < pivot1) {
1964 a[k] = a[less];
1965 a[less++] = a[great];
1966 } else { // a[great] == pivot1
1967 a[k] = pivot1;
1968 }
1969 a[great--] = ak;
1970 }
1971 }
1972
1973 // Sort left and right parts recursively
1974 dualPivotQuicksort(a, left, less - 1);
1975 dualPivotQuicksort(a, great + 1, right);
1976 }
1977 }
1978
1979 /**
1980 * Sorts the specified array into ascending numerical order.
1981 *
1982 * <p>The {@code <} relation does not provide a total order on all double
1983 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1984 * value compares neither less than, greater than, nor equal to any value,
1985 * even itself. This method uses the total order imposed by the method
1986 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1987 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1988 * other value and all {@code Double.NaN} values are considered equal.
1989 *
1990 * @param a the array to be sorted
1991 */
1992 public static void sort(double[] a) {
1993 sortNegZeroAndNaN(a, 0, a.length - 1);
1994 }
1995
1996 /**
1997 * Sorts the specified range of the array into ascending order. The range
1998 * to be sorted extends from the index {@code fromIndex}, inclusive, to
2014 * @throws ArrayIndexOutOfBoundsException
2015 * if {@code fromIndex < 0} or {@code toIndex > a.length}
2016 */
2017 public static void sort(double[] a, int fromIndex, int toIndex) {
2018 rangeCheck(a.length, fromIndex, toIndex);
2019 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
2020 }
2021
2022 /**
2023 * Sorts the specified range of the array into ascending order. The
2024 * sort is done in three phases to avoid expensive comparisons in the
2025 * inner loop. The comparisons would be expensive due to anomalies
2026 * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
2027 *
2028 * @param a the array to be sorted
2029 * @param left the index of the first element, inclusive, to be sorted
2030 * @param right the index of the last element, inclusive, to be sorted
2031 */
2032 private static void sortNegZeroAndNaN(double[] a, int left, int right) {
2033 /*
2034 * Phase 1: Count negative zeros and move NaNs to end of array.
2035 */
2036 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
2037 int numNegativeZeros = 0;
2038 int n = right;
2039
2040 for (int k = left; k <= n; k++) {
2041 double ak = a[k];
2042 if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
2043 a[k] = 0.0d;
2044 numNegativeZeros++;
2045 } else if (ak != ak) { // i.e., ak is NaN
2046 a[k--] = a[n];
2047 a[n--] = Double.NaN;
2048 }
2049 }
2050
2051 /*
2052 * Phase 2: Sort everything except NaNs (which are already in place).
2053 */
2054 dualPivotQuicksort(a, left, n);
2055
2056 /*
2057 * Phase 3: Turn positive zeros back into negative zeros.
2058 */
2059 if (numNegativeZeros == 0) {
2060 return;
2061 }
2062
2063 // Find first zero element
2064 int zeroIndex = findAnyZero(a, left, n);
2065
2066 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
2067 zeroIndex = i;
2068 }
2069
2070 // Turn the right number of positive zeros back into negative zeros
2071 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
2072 a[i] = -0.0d;
2073 }
2074 }
2075
2076 /**
2077 * Returns the index of some zero element in the specified range via
2081 * @param a the array to be searched
2082 * @param low the index of the first element, inclusive, to be searched
2083 * @param high the index of the last element, inclusive, to be searched
2084 */
2085 private static int findAnyZero(double[] a, int low, int high) {
2086 while (true) {
2087 int middle = (low + high) >>> 1;
2088 double middleValue = a[middle];
2089
2090 if (middleValue < 0.0d) {
2091 low = middle + 1;
2092 } else if (middleValue > 0.0d) {
2093 high = middle - 1;
2094 } else { // middleValue == 0.0d
2095 return middle;
2096 }
2097 }
2098 }
2099
2100 /**
2101 * Sorts the specified range of the array into ascending order by the
2102 * Dual-Pivot Quicksort algorithm.
2103 *
2104 * @param a the array to be sorted
2105 * @param left the index of the first element, inclusive, to be sorted
2106 * @param right the index of the last element, inclusive, to be sorted
2107 */
2108 private static void dualPivotQuicksort(double[] a, int left, int right) {
2109 int length = right - left + 1;
2110
2111 // Skip trivial arrays
2112 if (length < 2) {
2113 return;
2114 }
2115
2116 // Use insertion sort on tiny arrays
2117 if (length < INSERTION_SORT_THRESHOLD) {
2118 if (left > 0) {
2119 /*
2120 * Set negative infinity as a sentinel before the specified
2121 * range of the array, it allows to avoid expensive
2122 * check j >= left on each iteration.
2123 */
2124 double before = a[left-1];a[left-1] = Double.NEGATIVE_INFINITY;
2125
2126 for (int j, i = left + 1; i <= right; i++) {
2127 double ai = a[i];
2128 for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
2129 a[j + 1] = a[j];
2130 }
2131 a[j + 1] = ai;
2132 }
2133 a[left - 1] = before;
2134 } else {
2135 /*
2136 * For case, when left == 0, traditional (without a sentinel)
2137 * insertion sort, optimized for server VM, is used.
2138 */
2139 for (int i = 0, j = i; i < right; j = ++i) {
2140 double ai = a[i + 1];
2141 while (ai < a[j]) {
2142 a[j + 1] = a[j];
2143 if (j-- == 0) {
2144 break;
2145 }
2146 }
2147 a[j + 1] = ai;
2148 }
2149 }
2150 return;
2151 }
2152
2153 // Inexpensive approximation of one seventh
2154 int seventh = (length >>> 3) + (length >>> 6) + 1;
2155
2156 // Compute indices of 5 center evenly spaced elements
2157 int e3 = (left + right) >>> 1; // The midpoint
2158 int e2 = e3 - seventh, e1 = e2 - seventh;
2159 int e4 = e3 + seventh, e5 = e4 + seventh;
2160
2161 // Sort these elements using a 5-element sorting network
2162 double ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
2163
2164 if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
2165 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
2166 if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
2167 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
2168 if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
2169 if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
2170 if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
2171 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
2172 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
2173
2174 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
2175
2176 /*
2177 * Use the second and fourth of the five sorted elements as pivots.
2178 * These values are inexpensive approximations of the first and
2179 * second terciles of the array. Note that pivot1 <= pivot2.
2180 */
2181 double pivot1 = a[e2];
2182 double pivot2 = a[e4];
2183
2184 // Pointers
2185 int less = left; // The index of the first element of center part
2186 int great = right; // The index before the first element of right part
2187
2188 if (pivot1 < pivot2) {
2189 /*
2190 * The first and the last elements to be sorted are moved to the
2191 * locations formerly occupied by the pivots. When partitioning
2192 * is complete, the pivots are swapped back into their final
2193 * positions, and excluded from subsequent sorting.
2194 */
2195 a[e2] = a[less++];
2196 a[e4] = a[great--];
2197
2198 /*
2199 * Partitioning:
2200 *
2201 * left part center part right part
2202 * +--------------------------------------------------------------+
2203 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
2204 * +--------------------------------------------------------------+
2205 * ^ ^ ^
2206 * | | |
2207 * less k great
2208 *
2209 * Invariants:
2210 *
2211 * all in (left, less) < pivot1
2212 * pivot1 <= all in [less, k) <= pivot2
2213 * all in (great, right) > pivot2
2214 *
2215 * Pointer k is the first index of not inspected ?-part.
2216 */
2217 outer:
2218 for (int k = less; k <= great; k++) {
2219 double ak = a[k];
2220 if (ak < pivot1) { // Move a[k] to left part
2221 if (k != less) {
2222 a[k] = a[less];
2223 a[less] = ak;
2224 }
2225 less++;
2226 } else if (ak > pivot2) { // Move a[k] to right part
2227 while (a[great] > pivot2) {
2228 if (great-- == k) {
2229 break outer;
2230 }
2231 }
2232 if (a[great] < pivot1) {
2233 a[k] = a[less];
2234 a[less++] = a[great];
2235 } else { // pivot1 <= a[great] <= pivot2
2236 a[k] = a[great];
2237 }
2238 a[great--] = ak;
2239 }
2240 }
2241
2242 // Swap pivots into their final positions
2243 a[left] = a[less - 1]; a[less - 1] = pivot1;
2244 a[right] = a[great + 1]; a[great + 1] = pivot2;
2245
2246 // Sort left and right parts recursively, excluding known pivots
2247 dualPivotQuicksort(a, left, less - 2);
2248 dualPivotQuicksort(a, great + 2, right);
2249
2250 /*
2251 * If center part is too large (comprises > 5/7 of the array),
2252 * swap internal pivot values to ends.
2253 */
2254 if (great - less > 5 * seventh) {
2255 while (a[less] == pivot1) {
2256 less++;
2257 }
2258 while (a[great] == pivot2) {
2259 great--;
2260 }
2261
2262 /*
2263 * Partitioning:
2264 *
2265 * left part center part right part
2266 * +----------------------------------------------------------+
2267 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
2268 * +----------------------------------------------------------+
2269 * ^ ^ ^
2270 * | | |
2271 * less k great
2272 *
2273 * Invariants:
2274 *
2275 * all in (*, less) == pivot1
2276 * pivot1 < all in [less, k) < pivot2
2277 * all in (great, *) == pivot2
2278 *
2279 * Pointer k is the first index of not inspected ?-part.
2280 */
2281 outer:
2282 for (int k = less; k <= great; k++) {
2283 double ak = a[k];
2284 if (ak == pivot2) { // Move a[k] to right part
2285 while (a[great] == pivot2) {
2286 if (great-- == k) {
2287 break outer;
2288 }
2289 }
2290 if (a[great] == pivot1) {
2291 a[k] = a[less];
2292 a[less++] = pivot1;
2293 } else { // pivot1 < a[great] < pivot2
2294 a[k] = a[great];
2295 }
2296 a[great--] = pivot2;
2297 } else if (ak == pivot1) { // Move a[k] to left part
2298 a[k] = a[less];
2299 a[less++] = pivot1;
2300 }
2301 }
2302 }
2303
2304 // Sort center part recursively
2305 dualPivotQuicksort(a, less, great);
2306
2307 } else { // Pivots are equal
2308 /*
2309 * Partition degenerates to the traditional 3-way
2310 * (or "Dutch National Flag") schema:
2311 *
2312 * left part center part right part
2313 * +----------------------------------------------+
2314 * | < pivot | == pivot | ? | > pivot |
2315 * +----------------------------------------------+
2316 * ^ ^ ^
2317 * | | |
2318 * less k great
2319 *
2320 * Invariants:
2321 *
2322 * all in (left, less) < pivot
2323 * all in [less, k) == pivot
2324 * all in (great, right) > pivot
2325 *
2326 * Pointer k is the first index of not inspected ?-part.
2327 */
2328 for (int k = less; k <= great; k++) {
2329 double ak = a[k];
2330 if (ak == pivot1) {
2331 continue;
2332 }
2333 if (ak < pivot1) { // Move a[k] to left part
2334 if (k != less) {
2335 a[k] = a[less];
2336 a[less] = ak;
2337 }
2338 less++;
2339 } else { // a[k] > pivot1 - Move a[k] to right part
2340 /*
2341 * We know that pivot1 == a[e3] == pivot2. Thus, we know
2342 * that great will still be >= k when the following loop
2343 * terminates, even though we don't test for it explicitly.
2344 * In other words, a[e3] acts as a sentinel for great.
2345 */
2346 while (a[great] > pivot1) {
2347 great--;
2348 }
2349 if (a[great] < pivot1) {
2350 a[k] = a[less];
2351 a[less++] = a[great];
2352 } else { // a[great] == pivot1
2353 a[k] = pivot1;
2354 }
2355 a[great--] = ak;
2356 }
2357 }
2358
2359 // Sort left and right parts recursively
2360 dualPivotQuicksort(a, left, less - 1);
2361 dualPivotQuicksort(a, great + 1, right);
2362 }
2363 }
2364
2365 /**
2366 * Checks that {@code fromIndex} and {@code toIndex} are in
2367 * the range and throws an appropriate exception, if they aren't.
2368 */
2369 private static void rangeCheck(int length, int fromIndex, int toIndex) {
2370 if (fromIndex > toIndex) {
2371 throw new IllegalArgumentException(
2372 "fromIndex: " + fromIndex + " > toIndex: " + toIndex);
2373 }
2374 if (fromIndex < 0) {
2375 throw new ArrayIndexOutOfBoundsException(fromIndex);
2376 }
2377 if (toIndex > length) {
2378 throw new ArrayIndexOutOfBoundsException(toIndex);
2379 }
2380 }
2381 }
|