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