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.16 m765.827.v12a
40 */
41 final class DualPivotQuicksort {
42
43 /**
44 * Suppresses default constructor.
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 /**
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.
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 on
105 * {@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 k = left + 1; k <= right; k++) {
115 int ak = a[k];
116 int j;
117 for (j = k - 1; j >= left && ak < a[j]; j--) {
118 a[j + 1] = a[j];
119 }
120 a[j + 1] = ak;
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
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 sorted elements 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 /*
174 * Partitioning
175 *
176 * left part center part right part
177 * ------------------------------------------------------------
178 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
179 * ------------------------------------------------------------
180 * ^ ^ ^
181 * | | |
182 * less k great
183 */
184
185 // Pointers
186 int less = left + 1; // The index of first element of center part
187 int great = right - 1; // The index before first element of right part
188
189 boolean pivotsDiffer = pivot1 != pivot2;
190
191 if (pivotsDiffer) {
192 /*
193 * Invariants:
194 * all in (left, less) < pivot1
195 * pivot1 <= all in [less, k) <= pivot2
196 * all in (great, right) > pivot2
197 *
198 * Pointer k is the first index of ?-part
199 */
200 outer:
201 for (int k = less; k <= great; k++) {
202 int ak = a[k];
203 if (ak < pivot1) {
204 if (k > less) {
205 a[k] = a[less];
206 a[less] = ak;
207 }
208 less++;
209 } else if (ak > pivot2) {
210 while (a[great] > pivot2) {
211 if (k == great--) {
212 break outer;
213 }
214 }
215 a[k] = a[great];
216 a[great--] = ak;
217
218 if ((ak = a[k]) < pivot1) {
219 a[k] = a[less];
220 a[less++] = 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 * | | |
236 * less k great
237 *
238 * Invariants:
239 *
240 * all in (left, less) < pivot
241 * all in [less, k) == pivot
242 * all in (great, right) > pivot
243 *
244 * Pointer k is the first index of ?-part
245 */
246 outer:
247 for (int k = less; k <= great; k++) {
248 int ak = a[k];
249 if (ak == pivot1) {
250 continue;
251 }
252 if (ak < pivot1) {
253 if (k > less) {
254 a[k] = a[less];
255 a[less] = ak;
256 }
257 less++;
258 } else { // a[k] > pivot
259 while (a[great] > pivot1) {
260 if (k == great--) {
261 break outer;
262 }
263 }
264 a[k] = a[great];
265 a[great--] = ak;
266
267 if ((ak = a[k]) < pivot1) {
268 a[k] = a[less];
269 a[less++] = ak;
270 }
271 }
272 }
273 }
274
275 // Swap pivots into their final positions
276 a[left] = a[less - 1]; a[less - 1] = pivot1;
277 a[right] = a[great + 1]; a[great + 1] = pivot2;
278
279 // Sort left and right parts recursively, excluding known pivot values
280 doSort(a, left, less - 2);
281 doSort(a, great + 2, right);
282
283 /*
284 * If pivot1 == pivot2, all elements from center
285 * part are equal and, therefore, already sorted
286 */
287 if (!pivotsDiffer) {
288 return;
289 }
290
291 /*
292 * If center part is too large (comprises > 5/6 of
293 * the array), swap internal pivot values to ends
294 */
295 if (less < e1 && e5 < great) {
296 while (a[less] == pivot1) {
297 less++;
298 }
299 while (a[great] == pivot2) {
300 great--;
301 }
302 for (int k = less + 1; k <= great; ) {
303 int ak = a[k];
304 if (ak == pivot1) {
305 a[k++] = a[less];
306 a[less++] = pivot1;
307 } else if (ak == pivot2) {
308 a[k] = a[great];
309 a[great--] = pivot2;
310 } else {
311 k++;
312 }
313 }
314 }
315
316 // Sort center part recursively, excluding known pivot values
317 doSort(a, less, great);
318 }
319
320 /**
321 * Sorts the specified array into ascending numerical order.
322 *
323 * @param a the array to be sorted
324 */
325 public static void sort(long[] a) {
326 doSort(a, 0, a.length - 1);
327 }
328
329 /**
330 * Sorts the specified range of the array into ascending order. The range
331 * to be sorted extends from the index {@code fromIndex}, inclusive, to
332 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
333 * the range to be sorted is empty.
334 *
335 * @param a the array to be sorted
336 * @param fromIndex the index of the first element, inclusive, to be sorted
337 * @param toIndex the index of the last element, exclusive, to be sorted
338 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
339 * @throws ArrayIndexOutOfBoundsException
340 * if {@code fromIndex < 0} or {@code toIndex > a.length}
341 */
342 public static void sort(long[] a, int fromIndex, int toIndex) {
343 rangeCheck(a.length, fromIndex, toIndex);
344 doSort(a, fromIndex, toIndex - 1);
345 }
346
347 /**
348 * Sorts the specified range of the array into ascending order. This
349 * method differs from the public {@code sort} method in that the
350 * {@code right} index is inclusive, and it does no range checking on
351 * {@code left} or {@code right}.
352 *
353 * @param a the array to be sorted
354 * @param left the index of the first element, inclusive, to be sorted
355 * @param right the index of the last element, inclusive, to be sorted
356 */
357 private static void doSort(long[] a, int left, int right) {
358 // Use insertion sort on tiny arrays
359 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
360 for (int k = left + 1; k <= right; k++) {
361 long ak = a[k];
362 int j;
363 for (j = k - 1; j >= left && ak < a[j]; j--) {
364 a[j + 1] = a[j];
365 }
366 a[j + 1] = ak;
367 }
368 } else { // Use Dual-Pivot Quicksort on large arrays
369 dualPivotQuicksort(a, left, right);
370 }
371 }
372
373 /**
374 * Sorts the specified range of the array into ascending order by the
375 * Dual-Pivot Quicksort algorithm.
376 *
377 * @param a the array to be sorted
378 * @param left the index of the first element, inclusive, to be sorted
379 * @param right the index of the last element, inclusive, to be sorted
380 */
381 private static void dualPivotQuicksort(long[] a, int left, int right) {
382 // Compute indices of five evenly spaced elements
383 int sixth = (right - left + 1) / 6;
384 int e1 = left + sixth;
385 int e5 = right - sixth;
386 int e3 = (left + right) >>> 1; // The midpoint
391 long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
392
393 if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
394 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
395 if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
396 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
397 if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
398 if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
399 if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
400 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
401 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
402
403 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
404
405 /*
406 * Use the second and fourth of the five sorted elements as pivots.
407 * These values are inexpensive approximations of the first and
408 * second terciles of the array. Note that pivot1 <= pivot2.
409 *
410 * The pivots are stored in local variables, and the first and
411 * the last of the sorted elements are moved to the locations
412 * formerly occupied by the pivots. When partitioning is complete,
413 * the pivots are swapped back into their final positions, and
414 * excluded from subsequent sorting.
415 */
416 long pivot1 = ae2; a[e2] = a[left];
417 long pivot2 = ae4; a[e4] = a[right];
418
419 /*
420 * Partitioning
421 *
422 * left part center part right part
423 * ------------------------------------------------------------
424 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
425 * ------------------------------------------------------------
426 * ^ ^ ^
427 * | | |
428 * less k great
429 */
430
431 // Pointers
432 int less = left + 1; // The index of first element of center part
433 int great = right - 1; // The index before first element of right part
434
435 boolean pivotsDiffer = pivot1 != pivot2;
436
437 if (pivotsDiffer) {
438 /*
439 * Invariants:
440 * all in (left, less) < pivot1
441 * pivot1 <= all in [less, k) <= pivot2
442 * all in (great, right) > pivot2
443 *
444 * Pointer k is the first index of ?-part
445 */
446 outer:
447 for (int k = less; k <= great; k++) {
448 long ak = a[k];
449 if (ak < pivot1) {
450 if (k > less) {
451 a[k] = a[less];
452 a[less] = ak;
453 }
454 less++;
455 } else if (ak > pivot2) {
456 while (a[great] > pivot2) {
457 if (k == great--) {
458 break outer;
459 }
460 }
461 a[k] = a[great];
462 a[great--] = ak;
463
464 if ((ak = a[k]) < pivot1) {
465 a[k] = a[less];
466 a[less++] = ak;
467 }
468 }
469 }
470 } else { // Pivots are equal
471 /*
472 * Partition degenerates to the traditional 3-way
473 * (or "Dutch National Flag") partition:
474 *
475 * left part center part right part
476 * -------------------------------------------------
477 * [ < pivot | == pivot | ? | > pivot ]
478 * -------------------------------------------------
479 *
480 * ^ ^ ^
481 * | | |
482 * less k great
483 *
484 * Invariants:
485 *
486 * all in (left, less) < pivot
487 * all in [less, k) == pivot
488 * all in (great, right) > pivot
489 *
490 * Pointer k is the first index of ?-part
491 */
492 outer:
493 for (int k = less; k <= great; k++) {
494 long ak = a[k];
495 if (ak == pivot1) {
496 continue;
497 }
498 if (ak < pivot1) {
499 if (k > less) {
500 a[k] = a[less];
501 a[less] = ak;
502 }
503 less++;
504 } else { // a[k] > pivot
505 while (a[great] > pivot1) {
506 if (k == great--) {
507 break outer;
508 }
509 }
510 a[k] = a[great];
511 a[great--] = ak;
512
513 if ((ak = a[k]) < pivot1) {
514 a[k] = a[less];
515 a[less++] = ak;
516 }
517 }
518 }
519 }
520
521 // Swap pivots into their final positions
522 a[left] = a[less - 1]; a[less - 1] = pivot1;
523 a[right] = a[great + 1]; a[great + 1] = pivot2;
524
525 // Sort left and right parts recursively, excluding known pivot values
526 doSort(a, left, less - 2);
527 doSort(a, great + 2, right);
528
529 /*
530 * If pivot1 == pivot2, all elements from center
531 * part are equal and, therefore, already sorted
532 */
533 if (!pivotsDiffer) {
534 return;
535 }
536
537 /*
538 * If center part is too large (comprises > 5/6 of
539 * the array), swap internal pivot values to ends
540 */
541 if (less < e1 && e5 < great) {
542 while (a[less] == pivot1) {
543 less++;
544 }
545 while (a[great] == pivot2) {
546 great--;
547 }
548 for (int k = less + 1; k <= great; ) {
549 long ak = a[k];
550 if (ak == pivot1) {
551 a[k++] = a[less];
552 a[less++] = pivot1;
553 } else if (ak == pivot2) {
554 a[k] = a[great];
555 a[great--] = pivot2;
556 } else {
557 k++;
558 }
559 }
560 }
561
562 // Sort center part recursively, excluding known pivot values
563 doSort(a, less, great);
564 }
565
566 /**
567 * Sorts the specified array into ascending numerical order.
568 *
569 * @param a the array to be sorted
570 */
571 public static void sort(short[] a) {
572 doSort(a, 0, a.length - 1);
573 }
574
575 /**
576 * Sorts the specified range of the array into ascending order. The range
577 * to be sorted extends from the index {@code fromIndex}, inclusive, to
578 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
579 * the range to be sorted is empty.
580 *
581 * @param a the array to be sorted
582 * @param fromIndex the index of the first element, inclusive, to be sorted
583 * @param toIndex the index of the last element, exclusive, to be sorted
584 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
585 * @throws ArrayIndexOutOfBoundsException
586 * if {@code fromIndex < 0} or {@code toIndex > a.length}
587 */
588 public static void sort(short[] a, int fromIndex, int toIndex) {
589 rangeCheck(a.length, fromIndex, toIndex);
590 doSort(a, fromIndex, toIndex - 1);
591 }
592
593 /** The number of distinct short values. */
594 private static final int NUM_SHORT_VALUES = 1 << 16;
595
596 /**
597 * Sorts the specified range of the array into ascending order. This
598 * method differs from the public {@code sort} method in that the
599 * {@code right} index is inclusive, and it does no range checking on
600 * {@code left} or {@code right}.
601 *
602 * @param a the array to be sorted
603 * @param left the index of the first element, inclusive, to be sorted
604 * @param right the index of the last element, inclusive, to be sorted
605 */
606 private static void doSort(short[] a, int left, int right) {
607 // Use insertion sort on tiny arrays
608 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
609 for (int k = left + 1; k <= right; k++) {
610 short ak = a[k];
611 int j;
612 for (j = k - 1; j >= left && ak < a[j]; j--) {
613 a[j + 1] = a[j];
614 }
615 a[j + 1] = ak;
616 }
617 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
618 // Use counting sort on huge arrays
619 int[] count = new int[NUM_SHORT_VALUES];
620
621 for (int i = left; i <= right; i++) {
622 count[a[i] - Short.MIN_VALUE]++;
623 }
624 for (int i = 0, k = left; i < count.length && k <= right; i++) {
625 short value = (short) (i + Short.MIN_VALUE);
626
627 for (int s = count[i]; s > 0; s--) {
628 a[k++] = value;
629 }
630 }
631 } else { // Use Dual-Pivot Quicksort on large arrays
632 dualPivotQuicksort(a, left, right);
633 }
634 }
635
654 short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
655
656 if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
657 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
658 if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
659 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
660 if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
661 if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
662 if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
663 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
664 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
665
666 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
667
668 /*
669 * Use the second and fourth of the five sorted elements as pivots.
670 * These values are inexpensive approximations of the first and
671 * second terciles of the array. Note that pivot1 <= pivot2.
672 *
673 * The pivots are stored in local variables, and the first and
674 * the last of the sorted elements are moved to the locations
675 * formerly occupied by the pivots. When partitioning is complete,
676 * the pivots are swapped back into their final positions, and
677 * excluded from subsequent sorting.
678 */
679 short pivot1 = ae2; a[e2] = a[left];
680 short pivot2 = ae4; a[e4] = a[right];
681
682 /*
683 * Partitioning
684 *
685 * left part center part right part
686 * ------------------------------------------------------------
687 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
688 * ------------------------------------------------------------
689 * ^ ^ ^
690 * | | |
691 * less k great
692 */
693
694 // Pointers
695 int less = left + 1; // The index of first element of center part
696 int great = right - 1; // The index before first element of right part
697
698 boolean pivotsDiffer = pivot1 != pivot2;
699
700 if (pivotsDiffer) {
701 /*
702 * Invariants:
703 * all in (left, less) < pivot1
704 * pivot1 <= all in [less, k) <= pivot2
705 * all in (great, right) > pivot2
706 *
707 * Pointer k is the first index of ?-part
708 */
709 outer:
710 for (int k = less; k <= great; k++) {
711 short ak = a[k];
712 if (ak < pivot1) {
713 if (k > less) {
714 a[k] = a[less];
715 a[less] = ak;
716 }
717 less++;
718 } else if (ak > pivot2) {
719 while (a[great] > pivot2) {
720 if (k == great--) {
721 break outer;
722 }
723 }
724 a[k] = a[great];
725 a[great--] = ak;
726
727 if ((ak = a[k]) < pivot1) {
728 a[k] = a[less];
729 a[less++] = ak;
730 }
731 }
732 }
733 } else { // Pivots are equal
734 /*
735 * Partition degenerates to the traditional 3-way
736 * (or "Dutch National Flag") partition:
737 *
738 * left part center part right part
739 * -------------------------------------------------
740 * [ < pivot | == pivot | ? | > pivot ]
741 * -------------------------------------------------
742 *
743 * ^ ^ ^
744 * | | |
745 * less k great
746 *
747 * Invariants:
748 *
749 * all in (left, less) < pivot
750 * all in [less, k) == pivot
751 * all in (great, right) > pivot
752 *
753 * Pointer k is the first index of ?-part
754 */
755 outer:
756 for (int k = less; k <= great; k++) {
757 short ak = a[k];
758 if (ak == pivot1) {
759 continue;
760 }
761 if (ak < pivot1) {
762 if (k > less) {
763 a[k] = a[less];
764 a[less] = ak;
765 }
766 less++;
767 } else { // a[k] > pivot
768 while (a[great] > pivot1) {
769 if (k == great--) {
770 break outer;
771 }
772 }
773 a[k] = a[great];
774 a[great--] = ak;
775
776 if ((ak = a[k]) < pivot1) {
777 a[k] = a[less];
778 a[less++] = ak;
779 }
780 }
781 }
782 }
783
784 // Swap pivots into their final positions
785 a[left] = a[less - 1]; a[less - 1] = pivot1;
786 a[right] = a[great + 1]; a[great + 1] = pivot2;
787
788 // Sort left and right parts recursively, excluding known pivot values
789 doSort(a, left, less - 2);
790 doSort(a, great + 2, right);
791
792 /*
793 * If pivot1 == pivot2, all elements from center
794 * part are equal and, therefore, already sorted
795 */
796 if (!pivotsDiffer) {
797 return;
798 }
799
800 /*
801 * If center part is too large (comprises > 5/6 of
802 * the array), swap internal pivot values to ends
803 */
804 if (less < e1 && e5 < great) {
805 while (a[less] == pivot1) {
806 less++;
807 }
808 while (a[great] == pivot2) {
809 great--;
810 }
811 for (int k = less + 1; k <= great; ) {
812 short ak = a[k];
813 if (ak == pivot1) {
814 a[k++] = a[less];
815 a[less++] = pivot1;
816 } else if (ak == pivot2) {
817 a[k] = a[great];
818 a[great--] = pivot2;
819 } else {
820 k++;
821 }
822 }
823 }
824
825 // Sort center part recursively, excluding known pivot values
826 doSort(a, less, great);
827 }
828
829 /**
830 * Sorts the specified array into ascending numerical order.
831 *
832 * @param a the array to be sorted
833 */
834 public static void sort(char[] a) {
835 doSort(a, 0, a.length - 1);
836 }
837
838 /**
839 * Sorts the specified range of the array into ascending order. The range
840 * to be sorted extends from the index {@code fromIndex}, inclusive, to
841 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
842 * the range to be sorted is empty.
843 *
844 * @param a the array to be sorted
845 * @param fromIndex the index of the first element, inclusive, to be sorted
846 * @param toIndex the index of the last element, exclusive, to be sorted
847 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
848 * @throws ArrayIndexOutOfBoundsException
849 * if {@code fromIndex < 0} or {@code toIndex > a.length}
850 */
851 public static void sort(char[] a, int fromIndex, int toIndex) {
852 rangeCheck(a.length, fromIndex, toIndex);
853 doSort(a, fromIndex, toIndex - 1);
854 }
855
856 /** The number of distinct char values. */
857 private static final int NUM_CHAR_VALUES = 1 << 16;
858
859 /**
860 * Sorts the specified range of the array into ascending order. This
861 * method differs from the public {@code sort} method in that the
862 * {@code right} index is inclusive, and it does no range checking on
863 * {@code left} or {@code right}.
864 *
865 * @param a the array to be sorted
866 * @param left the index of the first element, inclusive, to be sorted
867 * @param right the index of the last element, inclusive, to be sorted
868 */
869 private static void doSort(char[] a, int left, int right) {
870 // Use insertion sort on tiny arrays
871 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
872 for (int k = left + 1; k <= right; k++) {
873 char ak = a[k];
874 int j;
875 for (j = k - 1; j >= left && ak < a[j]; j--) {
876 a[j + 1] = a[j];
877 }
878 a[j + 1] = ak;
879 }
880 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
881 // Use counting sort on huge arrays
882 int[] count = new int[NUM_CHAR_VALUES];
883
884 for (int i = left; i <= right; i++) {
885 count[a[i]]++;
886 }
887 for (int i = 0, k = left; i < count.length && k <= right; i++) {
888 for (int s = count[i]; s > 0; s--) {
889 a[k++] = (char) i;
890 }
891 }
892 } else { // Use Dual-Pivot Quicksort on large arrays
893 dualPivotQuicksort(a, left, right);
894 }
895 }
896
897 /**
898 * Sorts the specified range of the array into ascending order by the
915 char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
916
917 if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
918 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
919 if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
920 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
921 if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
922 if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
923 if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
924 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
925 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
926
927 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
928
929 /*
930 * Use the second and fourth of the five sorted elements as pivots.
931 * These values are inexpensive approximations of the first and
932 * second terciles of the array. Note that pivot1 <= pivot2.
933 *
934 * The pivots are stored in local variables, and the first and
935 * the last of the sorted elements are moved to the locations
936 * formerly occupied by the pivots. When partitioning is complete,
937 * the pivots are swapped back into their final positions, and
938 * excluded from subsequent sorting.
939 */
940 char pivot1 = ae2; a[e2] = a[left];
941 char pivot2 = ae4; a[e4] = a[right];
942
943 /*
944 * Partitioning
945 *
946 * left part center part right part
947 * ------------------------------------------------------------
948 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
949 * ------------------------------------------------------------
950 * ^ ^ ^
951 * | | |
952 * less k great
953 */
954
955 // Pointers
956 int less = left + 1; // The index of first element of center part
957 int great = right - 1; // The index before first element of right part
958
959 boolean pivotsDiffer = pivot1 != pivot2;
960
961 if (pivotsDiffer) {
962 /*
963 * Invariants:
964 * all in (left, less) < pivot1
965 * pivot1 <= all in [less, k) <= pivot2
966 * all in (great, right) > pivot2
967 *
968 * Pointer k is the first index of ?-part
969 */
970 outer:
971 for (int k = less; k <= great; k++) {
972 char ak = a[k];
973 if (ak < pivot1) {
974 if (k > less) {
975 a[k] = a[less];
976 a[less] = ak;
977 }
978 less++;
979 } else if (ak > pivot2) {
980 while (a[great] > pivot2) {
981 if (k == great--) {
982 break outer;
983 }
984 }
985 a[k] = a[great];
986 a[great--] = ak;
987
988 if ((ak = a[k]) < pivot1) {
989 a[k] = a[less];
990 a[less++] = ak;
991 }
992 }
993 }
994 } else { // Pivots are equal
995 /*
996 * Partition degenerates to the traditional 3-way
997 * (or "Dutch National Flag") partition:
998 *
999 * left part center part right part
1000 * -------------------------------------------------
1001 * [ < pivot | == pivot | ? | > pivot ]
1002 * -------------------------------------------------
1003 *
1004 * ^ ^ ^
1005 * | | |
1006 * less k great
1007 *
1008 * Invariants:
1009 *
1010 * all in (left, less) < pivot
1011 * all in [less, k) == pivot
1012 * all in (great, right) > pivot
1013 *
1014 * Pointer k is the first index of ?-part
1015 */
1016 outer:
1017 for (int k = less; k <= great; k++) {
1018 char ak = a[k];
1019 if (ak == pivot1) {
1020 continue;
1021 }
1022 if (ak < pivot1) {
1023 if (k > less) {
1024 a[k] = a[less];
1025 a[less] = ak;
1026 }
1027 less++;
1028 } else { // a[k] > pivot
1029 while (a[great] > pivot1) {
1030 if (k == great--) {
1031 break outer;
1032 }
1033 }
1034 a[k] = a[great];
1035 a[great--] = ak;
1036
1037 if ((ak = a[k]) < pivot1) {
1038 a[k] = a[less];
1039 a[less++] = ak;
1040 }
1041 }
1042 }
1043 }
1044
1045 // Swap pivots into their final positions
1046 a[left] = a[less - 1]; a[less - 1] = pivot1;
1047 a[right] = a[great + 1]; a[great + 1] = pivot2;
1048
1049 // Sort left and right parts recursively, excluding known pivot values
1050 doSort(a, left, less - 2);
1051 doSort(a, great + 2, right);
1052
1053 /*
1054 * If pivot1 == pivot2, all elements from center
1055 * part are equal and, therefore, already sorted
1056 */
1057 if (!pivotsDiffer) {
1058 return;
1059 }
1060
1061 /*
1062 * If center part is too large (comprises > 5/6 of
1063 * the array), swap internal pivot values to ends
1064 */
1065 if (less < e1 && e5 < great) {
1066 while (a[less] == pivot1) {
1067 less++;
1068 }
1069 while (a[great] == pivot2) {
1070 great--;
1071 }
1072 for (int k = less + 1; k <= great; ) {
1073 char ak = a[k];
1074 if (ak == pivot1) {
1075 a[k++] = a[less];
1076 a[less++] = pivot1;
1077 } else if (ak == pivot2) {
1078 a[k] = a[great];
1079 a[great--] = pivot2;
1080 } else {
1081 k++;
1082 }
1083 }
1084 }
1085
1086 // Sort center part recursively, excluding known pivot values
1087 doSort(a, less, great);
1088 }
1089
1090 /**
1091 * Sorts the specified array into ascending numerical order.
1092 *
1093 * @param a the array to be sorted
1094 */
1095 public static void sort(byte[] a) {
1096 doSort(a, 0, a.length - 1);
1097 }
1098
1099 /**
1100 * Sorts the specified range of the array into ascending order. The range
1101 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1102 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1103 * the range to be sorted is empty.
1104 *
1105 * @param a the array to be sorted
1106 * @param fromIndex the index of the first element, inclusive, to be sorted
1107 * @param toIndex the index of the last element, exclusive, to be sorted
1108 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1109 * @throws ArrayIndexOutOfBoundsException
1110 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1111 */
1112 public static void sort(byte[] a, int fromIndex, int toIndex) {
1113 rangeCheck(a.length, fromIndex, toIndex);
1114 doSort(a, fromIndex, toIndex - 1);
1115 }
1116
1117 /** The number of distinct byte values. */
1118 private static final int NUM_BYTE_VALUES = 1 << 8;
1119
1120 /**
1121 * Sorts the specified range of the array into ascending order. This
1122 * method differs from the public {@code sort} method in that the
1123 * {@code right} index is inclusive, and it does no range checking on
1124 * {@code left} or {@code right}.
1125 *
1126 * @param a the array to be sorted
1127 * @param left the index of the first element, inclusive, to be sorted
1128 * @param right the index of the last element, inclusive, to be sorted
1129 */
1130 private static void doSort(byte[] a, int left, int right) {
1131 // Use insertion sort on tiny arrays
1132 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1133 for (int k = left + 1; k <= right; k++) {
1134 byte ak = a[k];
1135 int j;
1136 for (j = k - 1; j >= left && ak < a[j]; j--) {
1137 a[j + 1] = a[j];
1138 }
1139 a[j + 1] = ak;
1140 }
1141 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
1142 // Use counting sort on huge arrays
1143 int[] count = new int[NUM_BYTE_VALUES];
1144
1145 for (int i = left; i <= right; i++) {
1146 count[a[i] - Byte.MIN_VALUE]++;
1147 }
1148 for (int i = 0, k = left; i < count.length && k <= right; i++) {
1149 byte value = (byte) (i + Byte.MIN_VALUE);
1150
1151 for (int s = count[i]; s > 0; s--) {
1152 a[k++] = value;
1153 }
1154 }
1155 } else { // Use Dual-Pivot Quicksort on large arrays
1156 dualPivotQuicksort(a, left, right);
1157 }
1158 }
1159
1178 byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1179
1180 if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
1181 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1182 if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
1183 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1184 if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
1185 if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
1186 if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
1187 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
1188 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
1189
1190 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1191
1192 /*
1193 * Use the second and fourth of the five sorted elements as pivots.
1194 * These values are inexpensive approximations of the first and
1195 * second terciles of the array. Note that pivot1 <= pivot2.
1196 *
1197 * The pivots are stored in local variables, and the first and
1198 * the last of the sorted elements are moved to the locations
1199 * formerly occupied by the pivots. When partitioning is complete,
1200 * the pivots are swapped back into their final positions, and
1201 * excluded from subsequent sorting.
1202 */
1203 byte pivot1 = ae2; a[e2] = a[left];
1204 byte pivot2 = ae4; a[e4] = a[right];
1205
1206 /*
1207 * Partitioning
1208 *
1209 * left part center part right part
1210 * ------------------------------------------------------------
1211 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1212 * ------------------------------------------------------------
1213 * ^ ^ ^
1214 * | | |
1215 * less k great
1216 */
1217
1218 // Pointers
1219 int less = left + 1; // The index of first element of center part
1220 int great = right - 1; // The index before first element of right part
1221
1222 boolean pivotsDiffer = pivot1 != pivot2;
1223
1224 if (pivotsDiffer) {
1225 /*
1226 * Invariants:
1227 * all in (left, less) < pivot1
1228 * pivot1 <= all in [less, k) <= pivot2
1229 * all in (great, right) > pivot2
1230 *
1231 * Pointer k is the first index of ?-part
1232 */
1233 outer:
1234 for (int k = less; k <= great; k++) {
1235 byte ak = a[k];
1236 if (ak < pivot1) {
1237 if (k > less) {
1238 a[k] = a[less];
1239 a[less] = ak;
1240 }
1241 less++;
1242 } else if (ak > pivot2) {
1243 while (a[great] > pivot2) {
1244 if (k == great--) {
1245 break outer;
1246 }
1247 }
1248 a[k] = a[great];
1249 a[great--] = ak;
1250
1251 if ((ak = a[k]) < pivot1) {
1252 a[k] = a[less];
1253 a[less++] = ak;
1254 }
1255 }
1256 }
1257 } else { // Pivots are equal
1258 /*
1259 * Partition degenerates to the traditional 3-way
1260 * (or "Dutch National Flag") partition:
1261 *
1262 * left part center part right part
1263 * -------------------------------------------------
1264 * [ < pivot | == pivot | ? | > pivot ]
1265 * -------------------------------------------------
1266 *
1267 * ^ ^ ^
1268 * | | |
1269 * less k great
1270 *
1271 * Invariants:
1272 *
1273 * all in (left, less) < pivot
1274 * all in [less, k) == pivot
1275 * all in (great, right) > pivot
1276 *
1277 * Pointer k is the first index of ?-part
1278 */
1279 outer:
1280 for (int k = less; k <= great; k++) {
1281 byte ak = a[k];
1282 if (ak == pivot1) {
1283 continue;
1284 }
1285 if (ak < pivot1) {
1286 if (k > less) {
1287 a[k] = a[less];
1288 a[less] = ak;
1289 }
1290 less++;
1291 } else { // a[k] > pivot
1292 while (a[great] > pivot1) {
1293 if (k == great--) {
1294 break outer;
1295 }
1296 }
1297 a[k] = a[great];
1298 a[great--] = ak;
1299
1300 if ((ak = a[k]) < pivot1) {
1301 a[k] = a[less];
1302 a[less++] = ak;
1303 }
1304 }
1305 }
1306 }
1307
1308 // Swap pivots into their final positions
1309 a[left] = a[less - 1]; a[less - 1] = pivot1;
1310 a[right] = a[great + 1]; a[great + 1] = pivot2;
1311
1312 // Sort left and right parts recursively, excluding known pivot values
1313 doSort(a, left, less - 2);
1314 doSort(a, great + 2, right);
1315
1316 /*
1317 * If pivot1 == pivot2, all elements from center
1318 * part are equal and, therefore, already sorted
1319 */
1320 if (!pivotsDiffer) {
1321 return;
1322 }
1323
1324 /*
1325 * If center part is too large (comprises > 5/6 of
1326 * the array), swap internal pivot values to ends
1327 */
1328 if (less < e1 && e5 < great) {
1329 while (a[less] == pivot1) {
1330 less++;
1331 }
1332 while (a[great] == pivot2) {
1333 great--;
1334 }
1335 for (int k = less + 1; k <= great; ) {
1336 byte ak = a[k];
1337 if (ak == pivot1) {
1338 a[k++] = a[less];
1339 a[less++] = pivot1;
1340 } else if (ak == pivot2) {
1341 a[k] = a[great];
1342 a[great--] = pivot2;
1343 } else {
1344 k++;
1345 }
1346 }
1347 }
1348
1349 // Sort center part recursively, excluding known pivot values
1350 doSort(a, less, great);
1351 }
1352
1353 /**
1354 * Sorts the specified array into ascending numerical order.
1355 *
1356 * <p>The {@code <} relation does not provide a total order on all float
1357 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1358 * value compares neither less than, greater than, nor equal to any value,
1359 * even itself. This method uses the total order imposed by the method
1360 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1361 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1362 * other value and all {@code Float.NaN} values are considered equal.
1363 *
1364 * @param a the array to be sorted
1365 */
1366 public static void sort(float[] a) {
1367 sortNegZeroAndNaN(a, 0, a.length - 1);
1368 }
1369
1370 /**
1371 * Sorts the specified range of the array into ascending order. The range
1372 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1373 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1374 * the range to be sorted is empty.
1375 *
1376 * <p>The {@code <} relation does not provide a total order on all float
1377 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1378 * value compares neither less than, greater than, nor equal to any value,
1379 * even itself. This method uses the total order imposed by the method
1380 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1381 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1382 * other value and all {@code Float.NaN} values are considered equal.
1383 *
1384 * @param a the array to be sorted
1385 * @param fromIndex the index of the first element, inclusive, to be sorted
1386 * @param toIndex the index of the last element, exclusive, to be sorted
1387 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1388 * @throws ArrayIndexOutOfBoundsException
1389 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1390 */
1391 public static void sort(float[] a, int fromIndex, int toIndex) {
1392 rangeCheck(a.length, fromIndex, toIndex);
1393 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
1394 }
1468 } else { // middleValue == 0.0f
1469 return middle;
1470 }
1471 }
1472 }
1473
1474 /**
1475 * Sorts the specified range of the array into ascending order. This
1476 * method differs from the public {@code sort} method in three ways:
1477 * {@code right} index is inclusive, it does no range checking on
1478 * {@code left} or {@code right}, and it does not handle negative
1479 * zeros or NaNs in the array.
1480 *
1481 * @param a the array to be sorted, which must not contain -0.0f or NaN
1482 * @param left the index of the first element, inclusive, to be sorted
1483 * @param right the index of the last element, inclusive, to be sorted
1484 */
1485 private static void doSort(float[] a, int left, int right) {
1486 // Use insertion sort on tiny arrays
1487 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1488 for (int k = left + 1; k <= right; k++) {
1489 float ak = a[k];
1490 int j;
1491 for (j = k - 1; j >= left && ak < a[j]; j--) {
1492 a[j + 1] = a[j];
1493 }
1494 a[j + 1] = ak;
1495 }
1496 } else { // Use Dual-Pivot Quicksort on large arrays
1497 dualPivotQuicksort(a, left, right);
1498 }
1499 }
1500
1501 /**
1502 * Sorts the specified range of the array into ascending order by the
1503 * Dual-Pivot Quicksort algorithm.
1504 *
1505 * @param a the array to be sorted
1506 * @param left the index of the first element, inclusive, to be sorted
1507 * @param right the index of the last element, inclusive, to be sorted
1508 */
1509 private static void dualPivotQuicksort(float[] a, int left, int right) {
1510 // Compute indices of five evenly spaced elements
1511 int sixth = (right - left + 1) / 6;
1512 int e1 = left + sixth;
1513 int e5 = right - sixth;
1514 int e3 = (left + right) >>> 1; // The midpoint
1519 float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1520
1521 if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
1522 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1523 if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
1524 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1525 if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
1526 if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
1527 if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
1528 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
1529 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
1530
1531 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1532
1533 /*
1534 * Use the second and fourth of the five sorted elements as pivots.
1535 * These values are inexpensive approximations of the first and
1536 * second terciles of the array. Note that pivot1 <= pivot2.
1537 *
1538 * The pivots are stored in local variables, and the first and
1539 * the last of the sorted elements are moved to the locations
1540 * formerly occupied by the pivots. When partitioning is complete,
1541 * the pivots are swapped back into their final positions, and
1542 * excluded from subsequent sorting.
1543 */
1544 float pivot1 = ae2; a[e2] = a[left];
1545 float pivot2 = ae4; a[e4] = a[right];
1546
1547 /*
1548 * Partitioning
1549 *
1550 * left part center part right part
1551 * ------------------------------------------------------------
1552 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1553 * ------------------------------------------------------------
1554 * ^ ^ ^
1555 * | | |
1556 * less k great
1557 */
1558
1559 // Pointers
1560 int less = left + 1; // The index of first element of center part
1561 int great = right - 1; // The index before first element of right part
1562
1563 boolean pivotsDiffer = pivot1 != pivot2;
1564
1565 if (pivotsDiffer) {
1566 /*
1567 * Invariants:
1568 * all in (left, less) < pivot1
1569 * pivot1 <= all in [less, k) <= pivot2
1570 * all in (great, right) > pivot2
1571 *
1572 * Pointer k is the first index of ?-part
1573 */
1574 outer:
1575 for (int k = less; k <= great; k++) {
1576 float ak = a[k];
1577 if (ak < pivot1) {
1578 if (k > less) {
1579 a[k] = a[less];
1580 a[less] = ak;
1581 }
1582 less++;
1583 } else if (ak > pivot2) {
1584 while (a[great] > pivot2) {
1585 if (k == great--) {
1586 break outer;
1587 }
1588 }
1589 a[k] = a[great];
1590 a[great--] = ak;
1591
1592 if ((ak = a[k]) < pivot1) {
1593 a[k] = a[less];
1594 a[less++] = ak;
1595 }
1596 }
1597 }
1598 } else { // Pivots are equal
1599 /*
1600 * Partition degenerates to the traditional 3-way
1601 * (or "Dutch National Flag") partition:
1602 *
1603 * left part center part right part
1604 * -------------------------------------------------
1605 * [ < pivot | == pivot | ? | > pivot ]
1606 * -------------------------------------------------
1607 *
1608 * ^ ^ ^
1609 * | | |
1610 * less k great
1611 *
1612 * Invariants:
1613 *
1614 * all in (left, less) < pivot
1615 * all in [less, k) == pivot
1616 * all in (great, right) > pivot
1617 *
1618 * Pointer k is the first index of ?-part
1619 */
1620 outer:
1621 for (int k = less; k <= great; k++) {
1622 float ak = a[k];
1623 if (ak == pivot1) {
1624 continue;
1625 }
1626 if (ak < pivot1) {
1627 if (k > less) {
1628 a[k] = a[less];
1629 a[less] = ak;
1630 }
1631 less++;
1632 } else { // a[k] > pivot
1633 while (a[great] > pivot1) {
1634 if (k == great--) {
1635 break outer;
1636 }
1637 }
1638 a[k] = a[great];
1639 a[great--] = ak;
1640
1641 if ((ak = a[k]) < pivot1) {
1642 a[k] = a[less];
1643 a[less++] = ak;
1644 }
1645 }
1646 }
1647 }
1648
1649 // Swap pivots into their final positions
1650 a[left] = a[less - 1]; a[less - 1] = pivot1;
1651 a[right] = a[great + 1]; a[great + 1] = pivot2;
1652
1653 // Sort left and right parts recursively, excluding known pivot values
1654 doSort(a, left, less - 2);
1655 doSort(a, great + 2, right);
1656
1657 /*
1658 * If pivot1 == pivot2, all elements from center
1659 * part are equal and, therefore, already sorted
1660 */
1661 if (!pivotsDiffer) {
1662 return;
1663 }
1664
1665 /*
1666 * If center part is too large (comprises > 5/6 of
1667 * the array), swap internal pivot values to ends
1668 */
1669 if (less < e1 && e5 < great) {
1670 while (a[less] == pivot1) {
1671 less++;
1672 }
1673 while (a[great] == pivot2) {
1674 great--;
1675 }
1676 for (int k = less + 1; k <= great; ) {
1677 float ak = a[k];
1678 if (ak == pivot1) {
1679 a[k++] = a[less];
1680 a[less++] = pivot1;
1681 } else if (ak == pivot2) {
1682 a[k] = a[great];
1683 a[great--] = pivot2;
1684 } else {
1685 k++;
1686 }
1687 }
1688 }
1689
1690 // Sort center part recursively, excluding known pivot values
1691 doSort(a, less, great);
1692 }
1693
1694 /**
1695 * Sorts the specified array into ascending numerical order.
1696 *
1697 * <p>The {@code <} relation does not provide a total order on all double
1698 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1699 * value compares neither less than, greater than, nor equal to any value,
1700 * even itself. This method uses the total order imposed by the method
1701 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1702 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1703 * other value and all {@code Double.NaN} values are considered equal.
1704 *
1705 * @param a the array to be sorted
1706 */
1707 public static void sort(double[] a) {
1708 sortNegZeroAndNaN(a, 0, a.length - 1);
1709 }
1710
1711 /**
1712 * Sorts the specified range of the array into ascending order. The range
1713 * to be sorted extends from the index {@code fromIndex}, inclusive, to
1714 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1715 * the range to be sorted is empty.
1716 *
1717 * <p>The {@code <} relation does not provide a total order on all double
1718 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1719 * value compares neither less than, greater than, nor equal to any value,
1720 * even itself. This method uses the total order imposed by the method
1721 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1722 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1723 * other value and all {@code Double.NaN} values are considered equal.
1724 *
1725 * @param a the array to be sorted
1726 * @param fromIndex the index of the first element, inclusive, to be sorted
1727 * @param toIndex the index of the last element, exclusive, to be sorted
1728 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1729 * @throws ArrayIndexOutOfBoundsException
1730 * if {@code fromIndex < 0} or {@code toIndex > a.length}
1731 */
1732 public static void sort(double[] a, int fromIndex, int toIndex) {
1733 rangeCheck(a.length, fromIndex, toIndex);
1734 sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
1735 }
1809 } else { // middleValue == 0.0d
1810 return middle;
1811 }
1812 }
1813 }
1814
1815 /**
1816 * Sorts the specified range of the array into ascending order. This
1817 * method differs from the public {@code sort} method in three ways:
1818 * {@code right} index is inclusive, it does no range checking on
1819 * {@code left} or {@code right}, and it does not handle negative
1820 * zeros or NaNs in the array.
1821 *
1822 * @param a the array to be sorted, which must not contain -0.0d and NaN
1823 * @param left the index of the first element, inclusive, to be sorted
1824 * @param right the index of the last element, inclusive, to be sorted
1825 */
1826 private static void doSort(double[] a, int left, int right) {
1827 // Use insertion sort on tiny arrays
1828 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1829 for (int k = left + 1; k <= right; k++) {
1830 double ak = a[k];
1831 int j;
1832 for (j = k - 1; j >= left && ak < a[j]; j--) {
1833 a[j + 1] = a[j];
1834 }
1835 a[j + 1] = ak;
1836 }
1837 } else { // Use Dual-Pivot Quicksort on large arrays
1838 dualPivotQuicksort(a, left, right);
1839 }
1840 }
1841
1842 /**
1843 * Sorts the specified range of the array into ascending order by the
1844 * Dual-Pivot Quicksort algorithm.
1845 *
1846 * @param a the array to be sorted
1847 * @param left the index of the first element, inclusive, to be sorted
1848 * @param right the index of the last element, inclusive, to be sorted
1849 */
1850 private static void dualPivotQuicksort(double[] a, int left, int right) {
1851 // Compute indices of five evenly spaced elements
1852 int sixth = (right - left + 1) / 6;
1853 int e1 = left + sixth;
1854 int e5 = right - sixth;
1855 int e3 = (left + right) >>> 1; // The midpoint
1860 double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
1861
1862 if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
1863 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
1864 if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
1865 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
1866 if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
1867 if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
1868 if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
1869 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
1870 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
1871
1872 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
1873
1874 /*
1875 * Use the second and fourth of the five sorted elements as pivots.
1876 * These values are inexpensive approximations of the first and
1877 * second terciles of the array. Note that pivot1 <= pivot2.
1878 *
1879 * The pivots are stored in local variables, and the first and
1880 * the last of the sorted elements are moved to the locations
1881 * formerly occupied by the pivots. When partitioning is complete,
1882 * the pivots are swapped back into their final positions, and
1883 * excluded from subsequent sorting.
1884 */
1885 double pivot1 = ae2; a[e2] = a[left];
1886 double pivot2 = ae4; a[e4] = a[right];
1887
1888 /*
1889 * Partitioning
1890 *
1891 * left part center part right part
1892 * ------------------------------------------------------------
1893 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1894 * ------------------------------------------------------------
1895 * ^ ^ ^
1896 * | | |
1897 * less k great
1898 */
1899
1900 // Pointers
1901 int less = left + 1; // The index of first element of center part
1902 int great = right - 1; // The index before first element of right part
1903
1904 boolean pivotsDiffer = pivot1 != pivot2;
1905
1906 if (pivotsDiffer) {
1907 /*
1908 * Invariants:
1909 * all in (left, less) < pivot1
1910 * pivot1 <= all in [less, k) <= pivot2
1911 * all in (great, right) > pivot2
1912 *
1913 * Pointer k is the first index of ?-part
1914 */
1915 outer:
1916 for (int k = less; k <= great; k++) {
1917 double ak = a[k];
1918 if (ak < pivot1) {
1919 if (k > less) {
1920 a[k] = a[less];
1921 a[less] = ak;
1922 }
1923 less++;
1924 } else if (ak > pivot2) {
1925 while (a[great] > pivot2) {
1926 if (k == great--) {
1927 break outer;
1928 }
1929 }
1930 a[k] = a[great];
1931 a[great--] = ak;
1932
1933 if ((ak = a[k]) < pivot1) {
1934 a[k] = a[less];
1935 a[less++] = ak;
1936 }
1937 }
1938 }
1939 } else { // Pivots are equal
1940 /*
1941 * Partition degenerates to the traditional 3-way
1942 * (or "Dutch National Flag") partition:
1943 *
1944 * left part center part right part
1945 * -------------------------------------------------
1946 * [ < pivot | == pivot | ? | > pivot ]
1947 * -------------------------------------------------
1948 *
1949 * ^ ^ ^
1950 * | | |
1951 * less k great
1952 *
1953 * Invariants:
1954 *
1955 * all in (left, less) < pivot
1956 * all in [less, k) == pivot
1957 * all in (great, right) > pivot
1958 *
1959 * Pointer k is the first index of ?-part
1960 */
1961 outer:
1962 for (int k = less; k <= great; k++) {
1963 double ak = a[k];
1964 if (ak == pivot1) {
1965 continue;
1966 }
1967 if (ak < pivot1) {
1968 if (k > less) {
1969 a[k] = a[less];
1970 a[less] = ak;
1971 }
1972 less++;
1973 } else { // a[k] > pivot
1974 while (a[great] > pivot1) {
1975 if (k == great--) {
1976 break outer;
1977 }
1978 }
1979 a[k] = a[great];
1980 a[great--] = ak;
1981
1982 if ((ak = a[k]) < pivot1) {
1983 a[k] = a[less];
1984 a[less++] = ak;
1985 }
1986 }
1987 }
1988 }
1989
1990 // Swap pivots into their final positions
1991 a[left] = a[less - 1]; a[less - 1] = pivot1;
1992 a[right] = a[great + 1]; a[great + 1] = pivot2;
1993
1994 // Sort left and right parts recursively, excluding known pivot values
1995 doSort(a, left, less - 2);
1996 doSort(a, great + 2, right);
1997
1998 /*
1999 * If pivot1 == pivot2, all elements from center
2000 * part are equal and, therefore, already sorted
2001 */
2002 if (!pivotsDiffer) {
2003 return;
2004 }
2005
2006 /*
2007 * If center part is too large (comprises > 5/6 of
2008 * the array), swap internal pivot values to ends
2009 */
2010 if (less < e1 && e5 < great) {
2011 while (a[less] == pivot1) {
2012 less++;
2013 }
2014 while (a[great] == pivot2) {
2015 great--;
2016 }
2017 for (int k = less + 1; k <= great; ) {
2018 double ak = a[k];
2019 if (ak == pivot1) {
2020 a[k++] = a[less];
2021 a[less++] = pivot1;
2022 } else if (ak == pivot2) {
2023 a[k] = a[great];
2024 a[great--] = pivot2;
2025 } else {
2026 k++;
2027 }
2028 }
2029 }
2030
2031 // Sort center part recursively, excluding known pivot values
2032 doSort(a, less, great);
2033 }
2034
2035 /**
2036 * Checks that {@code fromIndex} and {@code toIndex} are in
2037 * the range and throws an appropriate exception, if they aren't.
2038 */
2039 private static void rangeCheck(int length, int fromIndex, int toIndex) {
2040 if (fromIndex > toIndex) {
2041 throw new IllegalArgumentException(
2042 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
2043 }
2044 if (fromIndex < 0) {
2045 throw new ArrayIndexOutOfBoundsException(fromIndex);
2046 }
|
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 /**
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
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
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
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
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
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 }
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
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
1906 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1907 * the range to be sorted is empty (and the call is a no-op).
1908 *
1909 * <p>The {@code <} relation does not provide a total order on all double
1910 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1911 * value compares neither less than, greater than, nor equal to any value,
1912 * even itself. This method uses the total order imposed by the method
1913 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1914 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1915 * other value and all {@code Double.NaN} values are considered equal.
1916 *
1917 * @param a the array to be sorted
1918 * @param fromIndex the index of the first element, inclusive, to be sorted
1919 * @param toIndex the index of the last element, exclusive, to be sorted
1920 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
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 }
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
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 }
|