1 /*
2 * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package java.util;
27
28 /**
29 * This class implements the Dual-Pivot Quicksort algorithm by
30 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
31 * offers O(n log(n)) performance on many data sets that cause other
32 * quicksorts to degrade to quadratic performance, and is typically
33 * faster than traditional (one-pivot) Quicksort implementations.
34 *
35 * @author Vladimir Yaroslavskiy
36 * @author Jon Bentley
37 * @author Josh Bloch
38 *
39 * @version 2009.10.22 m765.827.v4
40 */
41 final class DualPivotQuicksort {
42
43 // Suppresses default constructor, ensuring non-instantiability.
44 private DualPivotQuicksort() {}
45
46 /*
47 * Tuning Parameters.
48 */
49
50 /**
51 * If the length of an array to be sorted is less than this
52 * constant, insertion sort is used in preference to Quicksort.
53 */
54 private static final int INSERTION_SORT_THRESHOLD = 32;
55
56 /**
57 * If the length of a byte array to be sorted is greater than
58 * this constant, counting sort is used in preference to Quicksort.
59 */
60 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
61
62 /**
63 * If the length of a short or char array to be sorted is greater
64 * than this constant, counting sort is used in preference to Quicksort.
65 */
66 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
67
68 /*
69 * Sorting methods for the seven primitive types.
70 */
71
72 /**
73 * Sorts the specified range of the array into ascending order.
74 *
75 * @param a the array to be sorted
76 * @param left the index of the first element, inclusively, to be sorted
77 * @param right the index of the last element, inclusively, to be sorted
78 */
79 static void sort(int[] a, int left, int right) {
80 // Use insertion sort on tiny arrays
81 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
82 for (int k = left + 1; k <= right; k++) {
83 int ak = a[k];
84 int j;
85
86 for (j = k - 1; j >= left && ak < a[j]; j--) {
87 a[j + 1] = a[j];
88 }
89 a[j + 1] = ak;
90 }
91 } else { // Use Dual-Pivot Quicksort on large arrays
92 dualPivotQuicksort(a, left, right);
93 }
94 }
95
96 /**
97 * Sorts the specified range of the array into ascending order
98 * by Dual-Pivot Quicksort.
99 *
100 * @param a the array to be sorted
101 * @param left the index of the first element, inclusively, to be sorted
102 * @param right the index of the last element, inclusively, to be sorted
103 */
104 private static void dualPivotQuicksort(int[] a, int left, int right) {
105 // Compute indices of five evenly spaced elements
106 int sixth = (right - left + 1) / 6;
107 int e1 = left + sixth;
108 int e5 = right - sixth;
109 int e3 = (left + right) >>> 1; // The midpoint
110 int e4 = e3 + sixth;
111 int e2 = e3 - sixth;
112
113 // Sort these elements in place using a 5-element sorting network
114 if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
115 if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
116 if (a[e1] > a[e3]) { int t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
117 if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
118 if (a[e1] > a[e4]) { int t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
119 if (a[e3] > a[e4]) { int t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
120 if (a[e2] > a[e5]) { int t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
121 if (a[e2] > a[e3]) { int t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
122 if (a[e4] > a[e5]) { int t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
123
124 /*
125 * Use the second and fourth of the five sorted elements as pivots.
126 * These values are inexpensive approximations of the first and
127 * second terciles of the array. Note that pivot1 <= pivot2.
128 *
129 * The pivots are stored in local variables, and the first and
130 * the last of the sorted elements are moved to the locations
131 * formerly occupied by the pivots. When partitioning is complete,
132 * the pivots are swapped back into their final positions, and
133 * excluded from subsequent sorting.
134 */
135 int pivot1 = a[e2]; a[e2] = a[left];
136 int pivot2 = a[e4]; a[e4] = a[right];
137
138 /*
139 * Partitioning
140 *
141 * left part center part right part
142 * ------------------------------------------------------------
143 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
144 * ------------------------------------------------------------
145 * ^ ^ ^
146 * | | |
147 * less k great
148 */
149
150 // Pointers
151 int less = left + 1; // The index of first element of center part
152 int great = right - 1; // The index before first element of right part
153
154 boolean pivotsDiffer = pivot1 != pivot2;
155
156 if (pivotsDiffer) {
157 /*
158 * Invariants:
159 * all in (left, less) < pivot1
160 * pivot1 <= all in [less, k) <= pivot2
161 * all in (great, right) > pivot2
162 *
163 * Pointer k is the first index of ?-part
164 */
165 for (int k = less; k <= great; k++) {
166 int ak = a[k];
167
168 if (ak < pivot1) {
169 a[k] = a[less];
170 a[less++] = ak;
171 } else if (ak > pivot2) {
172 while (a[great] > pivot2 && k < great) {
173 great--;
174 }
175 a[k] = a[great];
176 a[great--] = ak;
177 ak = a[k];
178
179 if (ak < pivot1) {
180 a[k] = a[less];
181 a[less++] = ak;
182 }
183 }
184 }
185 } else { // Pivots are equal
186 /*
187 * Partition degenerates to the traditional 3-way
188 * (or "Dutch National Flag") partition:
189 *
190 * left part center part right part
191 * -------------------------------------------------
192 * [ < pivot | == pivot | ? | > pivot ]
193 * -------------------------------------------------
194 *
195 * ^ ^ ^
196 * | | |
197 * less k great
198 *
199 * Invariants:
200 *
201 * all in (left, less) < pivot
202 * all in [less, k) == pivot
203 * all in (great, right) > pivot
204 *
205 * Pointer k is the first index of ?-part
206 */
207 for (int k = less; k <= great; k++) {
208 int ak = a[k];
209
210 if (ak == pivot1) {
211 continue;
212 }
213 if (ak < pivot1) {
214 a[k] = a[less];
215 a[less++] = ak;
216 } else {
217 while (a[great] > pivot1) {
218 great--;
219 }
220 a[k] = a[great];
221 a[great--] = ak;
222 ak = a[k];
223
224 if (ak < pivot1) {
225 a[k] = a[less];
226 a[less++] = ak;
227 }
228 }
229 }
230 }
231
232 // Swap pivots into their final positions
233 a[left] = a[less - 1]; a[less - 1] = pivot1;
234 a[right] = a[great + 1]; a[great + 1] = pivot2;
235
236 // Sort left and right parts recursively, excluding known pivot values
237 sort(a, left, less - 2);
238 sort(a, great + 2, right);
239
240 /*
241 * If pivot1 == pivot2, all elements from center
242 * part are equal and, therefore, already sorted
243 */
244 if (!pivotsDiffer) {
245 return;
246 }
247
248 /*
249 * If center part is too large (comprises > 5/6 of
250 * the array), swap internal pivot values to ends
251 */
252 if (less < e1 && e5 < great) {
253 while (a[less] == pivot1) {
254 less++;
255 }
256 for (int k = less + 1; k <= great; k++) {
257 if (a[k] == pivot1) {
258 a[k] = a[less];
259 a[less++] = pivot1;
260 }
261 }
262 while (a[great] == pivot2) {
263 great--;
264 }
265 for (int k = great - 1; k >= less; k--) {
266 if (a[k] == pivot2) {
267 a[k] = a[great];
268 a[great--] = pivot2;
269 }
270 }
271 }
272
273 // Sort center part recursively, excluding known pivot values
274 sort(a, less, great);
275 }
276
277 /**
278 * Sorts the specified range of the array into ascending order.
279 *
280 * @param a the array to be sorted
281 * @param left the index of the first element, inclusively, to be sorted
282 * @param right the index of the last element, inclusively, to be sorted
283 */
284 static void sort(long[] a, int left, int right) {
285 // Use insertion sort on tiny arrays
286 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
287 for (int k = left + 1; k <= right; k++) {
288 long ak = a[k];
289 int j;
290
291 for (j = k - 1; j >= left && ak < a[j]; j--) {
292 a[j + 1] = a[j];
293 }
294 a[j + 1] = ak;
295 }
296 } else { // Use Dual-Pivot Quicksort on large arrays
297 dualPivotQuicksort(a, left, right);
298 }
299 }
300
301 /**
302 * Sorts the specified range of the array into ascending order
303 * by Dual-Pivot Quicksort.
304 *
305 * @param a the array to be sorted
306 * @param left the index of the first element, inclusively, to be sorted
307 * @param right the index of the last element, inclusively, to be sorted
308 */
309 private static void dualPivotQuicksort(long[] a, int left, int right) {
310 // Compute indices of five evenly spaced elements
311 int sixth = (right - left + 1) / 6;
312 int e1 = left + sixth;
313 int e5 = right - sixth;
314 int e3 = (left + right) >>> 1; // The midpoint
315 int e4 = e3 + sixth;
316 int e2 = e3 - sixth;
317
318 // Sort these elements in place using a 5-element sorting network
319 if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
320 if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
321 if (a[e1] > a[e3]) { long t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
322 if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
323 if (a[e1] > a[e4]) { long t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
324 if (a[e3] > a[e4]) { long t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
325 if (a[e2] > a[e5]) { long t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
326 if (a[e2] > a[e3]) { long t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
327 if (a[e4] > a[e5]) { long t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
328
329 /*
330 * Use the second and fourth of the five sorted elements as pivots.
331 * These values are inexpensive approximations of the first and
332 * second terciles of the array. Note that pivot1 <= pivot2.
333 *
334 * The pivots are stored in local variables, and the first and
335 * the last of the sorted elements are moved to the locations
336 * formerly occupied by the pivots. When partitioning is complete,
337 * the pivots are swapped back into their final positions, and
338 * excluded from subsequent sorting.
339 */
340 long pivot1 = a[e2]; a[e2] = a[left];
341 long pivot2 = a[e4]; a[e4] = a[right];
342
343 /*
344 * Partitioning
345 *
346 * left part center part right part
347 * ------------------------------------------------------------
348 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
349 * ------------------------------------------------------------
350 * ^ ^ ^
351 * | | |
352 * less k great
353 */
354
355 // Pointers
356 int less = left + 1; // The index of first element of center part
357 int great = right - 1; // The index before first element of right part
358
359 boolean pivotsDiffer = pivot1 != pivot2;
360
361 if (pivotsDiffer) {
362 /*
363 * Invariants:
364 * all in (left, less) < pivot1
365 * pivot1 <= all in [less, k) <= pivot2
366 * all in (great, right) > pivot2
367 *
368 * Pointer k is the first index of ?-part
369 */
370 for (int k = less; k <= great; k++) {
371 long ak = a[k];
372
373 if (ak < pivot1) {
374 a[k] = a[less];
375 a[less++] = ak;
376 } else if (ak > pivot2) {
377 while (a[great] > pivot2 && k < great) {
378 great--;
379 }
380 a[k] = a[great];
381 a[great--] = ak;
382 ak = a[k];
383
384 if (ak < pivot1) {
385 a[k] = a[less];
386 a[less++] = ak;
387 }
388 }
389 }
390 } else { // Pivots are equal
391 /*
392 * Partition degenerates to the traditional 3-way
393 * (or "Dutch National Flag") partition:
394 *
395 * left part center part right part
396 * -------------------------------------------------
397 * [ < pivot | == pivot | ? | > pivot ]
398 * -------------------------------------------------
399 *
400 * ^ ^ ^
401 * | | |
402 * less k great
403 *
404 * Invariants:
405 *
406 * all in (left, less) < pivot
407 * all in [less, k) == pivot
408 * all in (great, right) > pivot
409 *
410 * Pointer k is the first index of ?-part
411 */
412 for (int k = less; k <= great; k++) {
413 long ak = a[k];
414
415 if (ak == pivot1) {
416 continue;
417 }
418 if (ak < pivot1) {
419 a[k] = a[less];
420 a[less++] = ak;
421 } else {
422 while (a[great] > pivot1) {
423 great--;
424 }
425 a[k] = a[great];
426 a[great--] = ak;
427 ak = a[k];
428
429 if (ak < pivot1) {
430 a[k] = a[less];
431 a[less++] = ak;
432 }
433 }
434 }
435 }
436
437 // Swap pivots into their final positions
438 a[left] = a[less - 1]; a[less - 1] = pivot1;
439 a[right] = a[great + 1]; a[great + 1] = pivot2;
440
441 // Sort left and right parts recursively, excluding known pivot values
442 sort(a, left, less - 2);
443 sort(a, great + 2, right);
444
445 /*
446 * If pivot1 == pivot2, all elements from center
447 * part are equal and, therefore, already sorted
448 */
449 if (!pivotsDiffer) {
450 return;
451 }
452
453 /*
454 * If center part is too large (comprises > 5/6 of
455 * the array), swap internal pivot values to ends
456 */
457 if (less < e1 && e5 < great) {
458 while (a[less] == pivot1) {
459 less++;
460 }
461 for (int k = less + 1; k <= great; k++) {
462 if (a[k] == pivot1) {
463 a[k] = a[less];
464 a[less++] = pivot1;
465 }
466 }
467 while (a[great] == pivot2) {
468 great--;
469 }
470 for (int k = great - 1; k >= less; k--) {
471 if (a[k] == pivot2) {
472 a[k] = a[great];
473 a[great--] = pivot2;
474 }
475 }
476 } else { // Use Dual-Pivot Quicksort on large arrays
477 dualPivotQuicksort(a, left, right);
478 }
479 }
480
481 /** The number of distinct short values */
482 private static final int NUM_SHORT_VALUES = 1 << 16;
483
484 /**
485 * Sorts the specified range of the array into ascending order.
486 *
487 * @param a the array to be sorted
488 * @param left the index of the first element, inclusively, to be sorted
489 * @param right the index of the last element, inclusively, to be sorted
490 */
491 static void sort(short[] a, int left, int right) {
492 // Use insertion sort on tiny arrays
493 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
494 for (int k = left + 1; k <= right; k++) {
495 short ak = a[k];
496 int j;
497
498 for (j = k - 1; j >= left && ak < a[j]; j--) {
499 a[j + 1] = a[j];
500 }
501 a[j + 1] = ak;
502 }
503 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
504 // Use counting sort on huge arrays
505 int[] count = new int[NUM_SHORT_VALUES];
506
507 for (int i = left; i <= right; i++) {
508 count[a[i] - Short.MIN_VALUE]++;
509 }
510 for (int i = 0, k = left; i < count.length && k < right; i++) {
511 short value = (short) (i + Short.MIN_VALUE);
512
513 for (int s = count[i]; s > 0; s--) {
514 a[k++] = value;
515 }
516 }
517 } else { // Use Dual-Pivot Quicksort on large arrays
518 dualPivotQuicksort(a, left, right);
519 }
520 }
521
522 /**
523 * Sorts the specified range of the array into ascending order
524 * by Dual-Pivot Quicksort.
525 *
526 * @param a the array to be sorted
527 * @param left the index of the first element, inclusively, to be sorted
528 * @param right the index of the last element, inclusively, to be sorted
529 */
530 private static void dualPivotQuicksort(short[] a, int left, int right) {
531 // Compute indices of five evenly spaced elements
532 int sixth = (right - left + 1) / 6;
533 int e1 = left + sixth;
534 int e5 = right - sixth;
535 int e3 = (left + right) >>> 1; // The midpoint
536 int e4 = e3 + sixth;
537 int e2 = e3 - sixth;
538
539 // Sort these elements in place using a 5-element sorting network
540 if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
541 if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
542 if (a[e1] > a[e3]) { short t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
543 if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
544 if (a[e1] > a[e4]) { short t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
545 if (a[e3] > a[e4]) { short t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
546 if (a[e2] > a[e5]) { short t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
547 if (a[e2] > a[e3]) { short t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
548 if (a[e4] > a[e5]) { short t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
549
550 /*
551 * Use the second and fourth of the five sorted elements as pivots.
552 * These values are inexpensive approximations of the first and
553 * second terciles of the array. Note that pivot1 <= pivot2.
554 *
555 * The pivots are stored in local variables, and the first and
556 * the last of the sorted elements are moved to the locations
557 * formerly occupied by the pivots. When partitioning is complete,
558 * the pivots are swapped back into their final positions, and
559 * excluded from subsequent sorting.
560 */
561 short pivot1 = a[e2]; a[e2] = a[left];
562 short pivot2 = a[e4]; a[e4] = a[right];
563
564 /*
565 * Partitioning
566 *
567 * left part center part right part
568 * ------------------------------------------------------------
569 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
570 * ------------------------------------------------------------
571 * ^ ^ ^
572 * | | |
573 * less k great
574 */
575
576 // Pointers
577 int less = left + 1; // The index of first element of center part
578 int great = right - 1; // The index before first element of right part
579
580 boolean pivotsDiffer = pivot1 != pivot2;
581
582 if (pivotsDiffer) {
583 /*
584 * Invariants:
585 * all in (left, less) < pivot1
586 * pivot1 <= all in [less, k) <= pivot2
587 * all in (great, right) > pivot2
588 *
589 * Pointer k is the first index of ?-part
590 */
591 for (int k = less; k <= great; k++) {
592 short ak = a[k];
593
594 if (ak < pivot1) {
595 a[k] = a[less];
596 a[less++] = ak;
597 } else if (ak > pivot2) {
598 while (a[great] > pivot2 && k < great) {
599 great--;
600 }
601 a[k] = a[great];
602 a[great--] = ak;
603 ak = a[k];
604
605 if (ak < pivot1) {
606 a[k] = a[less];
607 a[less++] = ak;
608 }
609 }
610 }
611 } else { // Pivots are equal
612 /*
613 * Partition degenerates to the traditional 3-way
614 * (or "Dutch National Flag") partition:
615 *
616 * left part center part right part
617 * -------------------------------------------------
618 * [ < pivot | == pivot | ? | > pivot ]
619 * -------------------------------------------------
620 *
621 * ^ ^ ^
622 * | | |
623 * less k great
624 *
625 * Invariants:
626 *
627 * all in (left, less) < pivot
628 * all in [less, k) == pivot
629 * all in (great, right) > pivot
630 *
631 * Pointer k is the first index of ?-part
632 */
633 for (int k = less; k <= great; k++) {
634 short ak = a[k];
635
636 if (ak == pivot1) {
637 continue;
638 }
639 if (ak < pivot1) {
640 a[k] = a[less];
641 a[less++] = ak;
642 } else {
643 while (a[great] > pivot1) {
644 great--;
645 }
646 a[k] = a[great];
647 a[great--] = ak;
648 ak = a[k];
649
650 if (ak < pivot1) {
651 a[k] = a[less];
652 a[less++] = ak;
653 }
654 }
655 }
656 }
657
658 // Swap pivots into their final positions
659 a[left] = a[less - 1]; a[less - 1] = pivot1;
660 a[right] = a[great + 1]; a[great + 1] = pivot2;
661
662 // Sort left and right parts recursively, excluding known pivot values
663 sort(a, left, less - 2);
664 sort(a, great + 2, right);
665
666 /*
667 * If pivot1 == pivot2, all elements from center
668 * part are equal and, therefore, already sorted
669 */
670 if (!pivotsDiffer) {
671 return;
672 }
673
674 /*
675 * If center part is too large (comprises > 5/6 of
676 * the array), swap internal pivot values to ends
677 */
678 if (less < e1 && e5 < great) {
679 while (a[less] == pivot1) {
680 less++;
681 }
682 for (int k = less + 1; k <= great; k++) {
683 if (a[k] == pivot1) {
684 a[k] = a[less];
685 a[less++] = pivot1;
686 }
687 }
688 while (a[great] == pivot2) {
689 great--;
690 }
691 for (int k = great - 1; k >= less; k--) {
692 if (a[k] == pivot2) {
693 a[k] = a[great];
694 a[great--] = pivot2;
695 }
696 }
697 }
698
699 // Sort center part recursively, excluding known pivot values
700 sort(a, less, great);
701 }
702
703 /** The number of distinct byte values */
704 private static final int NUM_BYTE_VALUES = 1 << 8;
705
706 /**
707 * Sorts the specified range of the array into ascending order.
708 *
709 * @param a the array to be sorted
710 * @param left the index of the first element, inclusively, to be sorted
711 * @param right the index of the last element, inclusively, to be sorted
712 */
713 static void sort(byte[] a, int left, int right) {
714 // Use insertion sort on tiny arrays
715 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
716 for (int k = left + 1; k <= right; k++) {
717 byte ak = a[k];
718 int j;
719
720 for (j = k - 1; j >= left && ak < a[j]; j--) {
721 a[j + 1] = a[j];
722 }
723 a[j + 1] = ak;
724 }
725 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
726 // Use counting sort on large arrays
727 int[] count = new int[NUM_BYTE_VALUES];
728
729 for (int i = left; i <= right; i++) {
730 count[a[i] - Byte.MIN_VALUE]++;
731 }
732 for (int i = 0, k = left; i < count.length && k < right; i++) {
733 byte value = (byte) (i + Byte.MIN_VALUE);
734
735 for (int s = count[i]; s > 0; s--) {
736 a[k++] = value;
737 }
738 }
739 } else { // Use Dual-Pivot Quicksort on large arrays
740 dualPivotQuicksort(a, left, right);
741 }
742 }
743
744 /**
745 * Sorts the specified range of the array into ascending order
746 * by Dual-Pivot Quicksort.
747 *
748 * @param a the array to be sorted
749 * @param left the index of the first element, inclusively, to be sorted
750 * @param right the index of the last element, inclusively, to be sorted
751 */
752 private static void dualPivotQuicksort(byte[] a, int left, int right) {
753 // Compute indices of five evenly spaced elements
754 int sixth = (right - left + 1) / 6;
755 int e1 = left + sixth;
756 int e5 = right - sixth;
757 int e3 = (left + right) >>> 1; // The midpoint
758 int e4 = e3 + sixth;
759 int e2 = e3 - sixth;
760
761 // Sort these elements in place using a 5-element sorting network
762 if (a[e1] > a[e2]) { byte t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
763 if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
764 if (a[e1] > a[e3]) { byte t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
765 if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
766 if (a[e1] > a[e4]) { byte t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
767 if (a[e3] > a[e4]) { byte t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
768 if (a[e2] > a[e5]) { byte t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
769 if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
770 if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
771
772 /*
773 * Use the second and fourth of the five sorted elements as pivots.
774 * These values are inexpensive approximations of the first and
775 * second terciles of the array. Note that pivot1 <= pivot2.
776 *
777 * The pivots are stored in local variables, and the first and
778 * the last of the sorted elements are moved to the locations
779 * formerly occupied by the pivots. When partitioning is complete,
780 * the pivots are swapped back into their final positions, and
781 * excluded from subsequent sorting.
782 */
783 byte pivot1 = a[e2]; a[e2] = a[left];
784 byte pivot2 = a[e4]; a[e4] = a[right];
785
786 /*
787 * Partitioning
788 *
789 * left part center part right part
790 * ------------------------------------------------------------
791 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
792 * ------------------------------------------------------------
793 * ^ ^ ^
794 * | | |
795 * less k great
796 */
797
798 // Pointers
799 int less = left + 1; // The index of first element of center part
800 int great = right - 1; // The index before first element of right part
801
802 boolean pivotsDiffer = pivot1 != pivot2;
803
804 if (pivotsDiffer) {
805 /*
806 * Invariants:
807 * all in (left, less) < pivot1
808 * pivot1 <= all in [less, k) <= pivot2
809 * all in (great, right) > pivot2
810 *
811 * Pointer k is the first index of ?-part
812 */
813 for (int k = less; k <= great; k++) {
814 byte ak = a[k];
815
816 if (ak < pivot1) {
817 a[k] = a[less];
818 a[less++] = ak;
819 } else if (ak > pivot2) {
820 while (a[great] > pivot2 && k < great) {
821 great--;
822 }
823 a[k] = a[great];
824 a[great--] = ak;
825 ak = a[k];
826
827 if (ak < pivot1) {
828 a[k] = a[less];
829 a[less++] = ak;
830 }
831 }
832 }
833 } else { // Pivots are equal
834 /*
835 * Partition degenerates to the traditional 3-way
836 * (or "Dutch National Flag") partition:
837 *
838 * left part center part right part
839 * -------------------------------------------------
840 * [ < pivot | == pivot | ? | > pivot ]
841 * -------------------------------------------------
842 *
843 * ^ ^ ^
844 * | | |
845 * less k great
846 *
847 * Invariants:
848 *
849 * all in (left, less) < pivot
850 * all in [less, k) == pivot
851 * all in (great, right) > pivot
852 *
853 * Pointer k is the first index of ?-part
854 */
855 for (int k = less; k <= great; k++) {
856 byte ak = a[k];
857
858 if (ak == pivot1) {
859 continue;
860 }
861 if (ak < pivot1) {
862 a[k] = a[less];
863 a[less++] = ak;
864 } else {
865 while (a[great] > pivot1) {
866 great--;
867 }
868 a[k] = a[great];
869 a[great--] = ak;
870 ak = a[k];
871
872 if (ak < pivot1) {
873 a[k] = a[less];
874 a[less++] = ak;
875 }
876 }
877 }
878 }
879
880 // Swap pivots into their final positions
881 a[left] = a[less - 1]; a[less - 1] = pivot1;
882 a[right] = a[great + 1]; a[great + 1] = pivot2;
883
884 // Sort left and right parts recursively, excluding known pivot values
885 sort(a, left, less - 2);
886 sort(a, great + 2, right);
887
888 /*
889 * If pivot1 == pivot2, all elements from center
890 * part are equal and, therefore, already sorted
891 */
892 if (!pivotsDiffer) {
893 return;
894 }
895
896 /*
897 * If center part is too large (comprises > 5/6 of
898 * the array), swap internal pivot values to ends
899 */
900 if (less < e1 && e5 < great) {
901 while (a[less] == pivot1) {
902 less++;
903 }
904 for (int k = less + 1; k <= great; k++) {
905 if (a[k] == pivot1) {
906 a[k] = a[less];
907 a[less++] = pivot1;
908 }
909 }
910 while (a[great] == pivot2) {
911 great--;
912 }
913 for (int k = great - 1; k >= less; k--) {
914 if (a[k] == pivot2) {
915 a[k] = a[great];
916 a[great--] = pivot2;
917 }
918 }
919 }
920
921 // Sort center part recursively, excluding known pivot values
922 sort(a, less, great);
923 }
924
925 /** The number of distinct char values */
926 private static final int NUM_CHAR_VALUES = 1 << 16;
927
928 /**
929 * Sorts the specified range of the array into ascending order.
930 *
931 * @param a the array to be sorted
932 * @param left the index of the first element, inclusively, to be sorted
933 * @param right the index of the last element, inclusively, to be sorted
934 */
935 static void sort(char[] a, int left, int right) {
936 // Use insertion sort on tiny arrays
937 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
938 for (int k = left + 1; k <= right; k++) {
939 char ak = a[k];
940 int j;
941
942 for (j = k - 1; j >= left && ak < a[j]; j--) {
943 a[j + 1] = a[j];
944 }
945 a[j + 1] = ak;
946 }
947 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
948 // Use counting sort on huge arrays
949 int[] count = new int[NUM_CHAR_VALUES];
950
951 for (int i = left; i <= right; i++) {
952 count[a[i]]++;
953 }
954 for (int i = 0, k = left; i < count.length && k < right; i++) {
955 for (int s = count[i]; s > 0; s--) {
956 a[k++] = (char) i;
957 }
958 }
959 } else { // Use Dual-Pivot Quicksort on large arrays
960 dualPivotQuicksort(a, left, right);
961 }
962 }
963
964 /**
965 * Sorts the specified range of the array into ascending order
966 * by Dual-Pivot Quicksort.
967 *
968 * @param a the array to be sorted
969 * @param left the index of the first element, inclusively, to be sorted
970 * @param right the index of the last element, inclusively, to be sorted
971 */
972 private static void dualPivotQuicksort(char[] a, int left, int right) {
973 // Compute indices of five evenly spaced elements
974 int sixth = (right - left + 1) / 6;
975 int e1 = left + sixth;
976 int e5 = right - sixth;
977 int e3 = (left + right) >>> 1; // The midpoint
978 int e4 = e3 + sixth;
979 int e2 = e3 - sixth;
980
981 // Sort these elements in place using a 5-element sorting network
982 if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
983 if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
984 if (a[e1] > a[e3]) { char t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
985 if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
986 if (a[e1] > a[e4]) { char t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
987 if (a[e3] > a[e4]) { char t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
988 if (a[e2] > a[e5]) { char t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
989 if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
990 if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
991
992 /*
993 * Use the second and fourth of the five sorted elements as pivots.
994 * These values are inexpensive approximations of the first and
995 * second terciles of the array. Note that pivot1 <= pivot2.
996 *
997 * The pivots are stored in local variables, and the first and
998 * the last of the sorted elements are moved to the locations
999 * formerly occupied by the pivots. When partitioning is complete,
1000 * the pivots are swapped back into their final positions, and
1001 * excluded from subsequent sorting.
1002 */
1003 char pivot1 = a[e2]; a[e2] = a[left];
1004 char pivot2 = a[e4]; a[e4] = a[right];
1005
1006 /*
1007 * Partitioning
1008 *
1009 * left part center part right part
1010 * ------------------------------------------------------------
1011 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1012 * ------------------------------------------------------------
1013 * ^ ^ ^
1014 * | | |
1015 * less k great
1016 */
1017
1018 // Pointers
1019 int less = left + 1; // The index of first element of center part
1020 int great = right - 1; // The index before first element of right part
1021
1022 boolean pivotsDiffer = pivot1 != pivot2;
1023
1024 if (pivotsDiffer) {
1025 /*
1026 * Invariants:
1027 * all in (left, less) < pivot1
1028 * pivot1 <= all in [less, k) <= pivot2
1029 * all in (great, right) > pivot2
1030 *
1031 * Pointer k is the first index of ?-part
1032 */
1033 for (int k = less; k <= great; k++) {
1034 char ak = a[k];
1035
1036 if (ak < pivot1) {
1037 a[k] = a[less];
1038 a[less++] = ak;
1039 } else if (ak > pivot2) {
1040 while (a[great] > pivot2 && k < great) {
1041 great--;
1042 }
1043 a[k] = a[great];
1044 a[great--] = ak;
1045 ak = a[k];
1046
1047 if (ak < pivot1) {
1048 a[k] = a[less];
1049 a[less++] = ak;
1050 }
1051 }
1052 }
1053 } else { // Pivots are equal
1054 /*
1055 * Partition degenerates to the traditional 3-way
1056 * (or "Dutch National Flag") partition:
1057 *
1058 * left part center part right part
1059 * -------------------------------------------------
1060 * [ < pivot | == pivot | ? | > pivot ]
1061 * -------------------------------------------------
1062 *
1063 * ^ ^ ^
1064 * | | |
1065 * less k great
1066 *
1067 * Invariants:
1068 *
1069 * all in (left, less) < pivot
1070 * all in [less, k) == pivot
1071 * all in (great, right) > pivot
1072 *
1073 * Pointer k is the first index of ?-part
1074 */
1075 for (int k = less; k <= great; k++) {
1076 char ak = a[k];
1077
1078 if (ak == pivot1) {
1079 continue;
1080 }
1081 if (ak < pivot1) {
1082 a[k] = a[less];
1083 a[less++] = ak;
1084 } else {
1085 while (a[great] > pivot1) {
1086 great--;
1087 }
1088 a[k] = a[great];
1089 a[great--] = ak;
1090 ak = a[k];
1091
1092 if (ak < pivot1) {
1093 a[k] = a[less];
1094 a[less++] = ak;
1095 }
1096 }
1097 }
1098 }
1099
1100 // Swap pivots into their final positions
1101 a[left] = a[less - 1]; a[less - 1] = pivot1;
1102 a[right] = a[great + 1]; a[great + 1] = pivot2;
1103
1104 // Sort left and right parts recursively, excluding known pivot values
1105 sort(a, left, less - 2);
1106 sort(a, great + 2, right);
1107
1108 /*
1109 * If pivot1 == pivot2, all elements from center
1110 * part are equal and, therefore, already sorted
1111 */
1112 if (!pivotsDiffer) {
1113 return;
1114 }
1115
1116 /*
1117 * If center part is too large (comprises > 5/6 of
1118 * the array), swap internal pivot values to ends
1119 */
1120 if (less < e1 && e5 < great) {
1121 while (a[less] == pivot1) {
1122 less++;
1123 }
1124 for (int k = less + 1; k <= great; k++) {
1125 if (a[k] == pivot1) {
1126 a[k] = a[less];
1127 a[less++] = pivot1;
1128 }
1129 }
1130 while (a[great] == pivot2) {
1131 great--;
1132 }
1133 for (int k = great - 1; k >= less; k--) {
1134 if (a[k] == pivot2) {
1135 a[k] = a[great];
1136 a[great--] = pivot2;
1137 }
1138 }
1139 }
1140
1141 // Sort center part recursively, excluding known pivot values
1142 sort(a, less, great);
1143 }
1144
1145 /**
1146 * Sorts the specified range of the array into ascending order.
1147 *
1148 * @param a the array to be sorted
1149 * @param left the index of the first element, inclusively, to be sorted
1150 * @param right the index of the last element, inclusively, to be sorted
1151 */
1152 static void sort(float[] a, int left, int right) {
1153 // Use insertion sort on tiny arrays
1154 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1155 for (int k = left + 1; k <= right; k++) {
1156 float ak = a[k];
1157 int j;
1158
1159 for (j = k - 1; j >= left && ak < a[j]; j--) {
1160 a[j + 1] = a[j];
1161 }
1162 a[j + 1] = ak;
1163 }
1164 } else { // Use Dual-Pivot Quicksort on large arrays
1165 dualPivotQuicksort(a, left, right);
1166 }
1167 }
1168
1169 /**
1170 * Sorts the specified range of the array into ascending order
1171 * by Dual-Pivot Quicksort.
1172 *
1173 * @param a the array to be sorted
1174 * @param left the index of the first element, inclusively, to be sorted
1175 * @param right the index of the last element, inclusively, to be sorted
1176 */
1177 private static void dualPivotQuicksort(float[] a, int left, int right) {
1178 // Compute indices of five evenly spaced elements
1179 int sixth = (right - left + 1) / 6;
1180 int e1 = left + sixth;
1181 int e5 = right - sixth;
1182 int e3 = (left + right) >>> 1; // The midpoint
1183 int e4 = e3 + sixth;
1184 int e2 = e3 - sixth;
1185
1186 // Sort these elements in place using a 5-element sorting network
1187 if (a[e1] > a[e2]) { float t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
1188 if (a[e4] > a[e5]) { float t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
1189 if (a[e1] > a[e3]) { float t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
1190 if (a[e2] > a[e3]) { float t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
1191 if (a[e1] > a[e4]) { float t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
1192 if (a[e3] > a[e4]) { float t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
1193 if (a[e2] > a[e5]) { float t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
1194 if (a[e2] > a[e3]) { float t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
1195 if (a[e4] > a[e5]) { float t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
1196
1197 /*
1198 * Use the second and fourth of the five sorted elements as pivots.
1199 * These values are inexpensive approximations of the first and
1200 * second terciles of the array. Note that pivot1 <= pivot2.
1201 *
1202 * The pivots are stored in local variables, and the first and
1203 * the last of the sorted elements are moved to the locations
1204 * formerly occupied by the pivots. When partitioning is complete,
1205 * the pivots are swapped back into their final positions, and
1206 * excluded from subsequent sorting.
1207 */
1208 float pivot1 = a[e2]; a[e2] = a[left];
1209 float pivot2 = a[e4]; a[e4] = a[right];
1210
1211 /*
1212 * Partitioning
1213 *
1214 * left part center part right part
1215 * ------------------------------------------------------------
1216 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1217 * ------------------------------------------------------------
1218 * ^ ^ ^
1219 * | | |
1220 * less k great
1221 */
1222
1223 // Pointers
1224 int less = left + 1; // The index of first element of center part
1225 int great = right - 1; // The index before first element of right part
1226
1227 boolean pivotsDiffer = pivot1 != pivot2;
1228
1229 if (pivotsDiffer) {
1230 /*
1231 * Invariants:
1232 * all in (left, less) < pivot1
1233 * pivot1 <= all in [less, k) <= pivot2
1234 * all in (great, right) > pivot2
1235 *
1236 * Pointer k is the first index of ?-part
1237 */
1238 for (int k = less; k <= great; k++) {
1239 float ak = a[k];
1240
1241 if (ak < pivot1) {
1242 a[k] = a[less];
1243 a[less++] = ak;
1244 } else if (ak > pivot2) {
1245 while (a[great] > pivot2 && k < great) {
1246 great--;
1247 }
1248 a[k] = a[great];
1249 a[great--] = ak;
1250 ak = a[k];
1251
1252 if (ak < pivot1) {
1253 a[k] = a[less];
1254 a[less++] = ak;
1255 }
1256 }
1257 }
1258 } else { // Pivots are equal
1259 /*
1260 * Partition degenerates to the traditional 3-way
1261 * (or "Dutch National Flag") partition:
1262 *
1263 * left part center part right part
1264 * -------------------------------------------------
1265 * [ < pivot | == pivot | ? | > pivot ]
1266 * -------------------------------------------------
1267 *
1268 * ^ ^ ^
1269 * | | |
1270 * less k great
1271 *
1272 * Invariants:
1273 *
1274 * all in (left, less) < pivot
1275 * all in [less, k) == pivot
1276 * all in (great, right) > pivot
1277 *
1278 * Pointer k is the first index of ?-part
1279 */
1280 for (int k = less; k <= great; k++) {
1281 float ak = a[k];
1282
1283 if (ak == pivot1) {
1284 continue;
1285 }
1286 if (ak < pivot1) {
1287 a[k] = a[less];
1288 a[less++] = ak;
1289 } else {
1290 while (a[great] > pivot1) {
1291 great--;
1292 }
1293 a[k] = a[great];
1294 a[great--] = ak;
1295 ak = a[k];
1296
1297 if (ak < pivot1) {
1298 a[k] = a[less];
1299 a[less++] = ak;
1300 }
1301 }
1302 }
1303 }
1304
1305 // Swap pivots into their final positions
1306 a[left] = a[less - 1]; a[less - 1] = pivot1;
1307 a[right] = a[great + 1]; a[great + 1] = pivot2;
1308
1309 // Sort left and right parts recursively, excluding known pivot values
1310 sort(a, left, less - 2);
1311 sort(a, great + 2, right);
1312
1313 /*
1314 * If pivot1 == pivot2, all elements from center
1315 * part are equal and, therefore, already sorted
1316 */
1317 if (!pivotsDiffer) {
1318 return;
1319 }
1320
1321 /*
1322 * If center part is too large (comprises > 5/6 of
1323 * the array), swap internal pivot values to ends
1324 */
1325 if (less < e1 && e5 < great) {
1326 while (a[less] == pivot1) {
1327 less++;
1328 }
1329 for (int k = less + 1; k <= great; k++) {
1330 if (a[k] == pivot1) {
1331 a[k] = a[less];
1332 a[less++] = pivot1;
1333 }
1334 }
1335 while (a[great] == pivot2) {
1336 great--;
1337 }
1338 for (int k = great - 1; k >= less; k--) {
1339 if (a[k] == pivot2) {
1340 a[k] = a[great];
1341 a[great--] = pivot2;
1342 }
1343 }
1344 }
1345
1346 // Sort center part recursively, excluding known pivot values
1347 sort(a, less, great);
1348 }
1349
1350 /**
1351 * Sorts the specified range of the array into ascending order.
1352 *
1353 * @param a the array to be sorted
1354 * @param left the index of the first element, inclusively, to be sorted
1355 * @param right the index of the last element, inclusively, to be sorted
1356 */
1357 static void sort(double[] a, int left, int right) {
1358 // Use insertion sort on tiny arrays
1359 if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
1360 for (int k = left + 1; k <= right; k++) {
1361 double ak = a[k];
1362 int j;
1363
1364 for (j = k - 1; j >= left && ak < a[j]; j--) {
1365 a[j + 1] = a[j];
1366 }
1367 a[j + 1] = ak;
1368 }
1369 } else { // Use Dual-Pivot Quicksort on large arrays
1370 dualPivotQuicksort(a, left, right);
1371 }
1372 }
1373
1374 /**
1375 * Sorts the specified range of the array into ascending order
1376 * by Dual-Pivot Quicksort.
1377 *
1378 * @param a the array to be sorted
1379 * @param left the index of the first element, inclusively, to be sorted
1380 * @param right the index of the last element, inclusively, to be sorted
1381 */
1382 private static void dualPivotQuicksort(double[] a, int left, int right) {
1383 // Compute indices of five evenly spaced elements
1384 int sixth = (right - left + 1) / 6;
1385 int e1 = left + sixth;
1386 int e5 = right - sixth;
1387 int e3 = (left + right) >>> 1; // The midpoint
1388 int e4 = e3 + sixth;
1389 int e2 = e3 - sixth;
1390
1391 // Sort these elements in place using a 5-element sorting network
1392 if (a[e1] > a[e2]) { double t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
1393 if (a[e4] > a[e5]) { double t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
1394 if (a[e1] > a[e3]) { double t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
1395 if (a[e2] > a[e3]) { double t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
1396 if (a[e1] > a[e4]) { double t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
1397 if (a[e3] > a[e4]) { double t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
1398 if (a[e2] > a[e5]) { double t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
1399 if (a[e2] > a[e3]) { double t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
1400 if (a[e4] > a[e5]) { double t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
1401
1402 /*
1403 * Use the second and fourth of the five sorted elements as pivots.
1404 * These values are inexpensive approximations of the first and
1405 * second terciles of the array. Note that pivot1 <= pivot2.
1406 *
1407 * The pivots are stored in local variables, and the first and
1408 * the last of the sorted elements are moved to the locations
1409 * formerly occupied by the pivots. When partitioning is complete,
1410 * the pivots are swapped back into their final positions, and
1411 * excluded from subsequent sorting.
1412 */
1413 double pivot1 = a[e2]; a[e2] = a[left];
1414 double pivot2 = a[e4]; a[e4] = a[right];
1415
1416 /*
1417 * Partitioning
1418 *
1419 * left part center part right part
1420 * ------------------------------------------------------------
1421 * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
1422 * ------------------------------------------------------------
1423 * ^ ^ ^
1424 * | | |
1425 * less k great
1426 */
1427
1428 // Pointers
1429 int less = left + 1; // The index of first element of center part
1430 int great = right - 1; // The index before first element of right part
1431
1432 boolean pivotsDiffer = pivot1 != pivot2;
1433
1434 if (pivotsDiffer) {
1435 /*
1436 * Invariants:
1437 * all in (left, less) < pivot1
1438 * pivot1 <= all in [less, k) <= pivot2
1439 * all in (great, right) > pivot2
1440 *
1441 * Pointer k is the first index of ?-part
1442 */
1443 for (int k = less; k <= great; k++) {
1444 double ak = a[k];
1445
1446 if (ak < pivot1) {
1447 a[k] = a[less];
1448 a[less++] = ak;
1449 } else if (ak > pivot2) {
1450 while (a[great] > pivot2 && k < great) {
1451 great--;
1452 }
1453 a[k] = a[great];
1454 a[great--] = ak;
1455 ak = a[k];
1456
1457 if (ak < pivot1) {
1458 a[k] = a[less];
1459 a[less++] = ak;
1460 }
1461 }
1462 }
1463 } else { // Pivots are equal
1464 /*
1465 * Partition degenerates to the traditional 3-way
1466 * (or "Dutch National Flag") partition:
1467 *
1468 * left part center part right part
1469 * -------------------------------------------------
1470 * [ < pivot | == pivot | ? | > pivot ]
1471 * -------------------------------------------------
1472 *
1473 * ^ ^ ^
1474 * | | |
1475 * less k great
1476 *
1477 * Invariants:
1478 *
1479 * all in (left, less) < pivot
1480 * all in [less, k) == pivot
1481 * all in (great, right) > pivot
1482 *
1483 * Pointer k is the first index of ?-part
1484 */
1485 for (int k = less; k <= great; k++) {
1486 double ak = a[k];
1487
1488 if (ak == pivot1) {
1489 continue;
1490 }
1491 if (ak < pivot1) {
1492 a[k] = a[less];
1493 a[less++] = ak;
1494 } else {
1495 while (a[great] > pivot1) {
1496 great--;
1497 }
1498 a[k] = a[great];
1499 a[great--] = ak;
1500 ak = a[k];
1501
1502 if (ak < pivot1) {
1503 a[k] = a[less];
1504 a[less++] = ak;
1505 }
1506 }
1507 }
1508 }
1509
1510 // Swap pivots into their final positions
1511 a[left] = a[less - 1]; a[less - 1] = pivot1;
1512 a[right] = a[great + 1]; a[great + 1] = pivot2;
1513
1514 // Sort left and right parts recursively, excluding known pivot values
1515 sort(a, left, less - 2);
1516 sort(a, great + 2, right);
1517
1518 /*
1519 * If pivot1 == pivot2, all elements from center
1520 * part are equal and, therefore, already sorted
1521 */
1522 if (!pivotsDiffer) {
1523 return;
1524 }
1525
1526 /*
1527 * If center part is too large (comprises > 5/6 of
1528 * the array), swap internal pivot values to ends
1529 */
1530 if (less < e1 && e5 < great) {
1531 while (a[less] == pivot1) {
1532 less++;
1533 }
1534 for (int k = less + 1; k <= great; k++) {
1535 if (a[k] == pivot1) {
1536 a[k] = a[less];
1537 a[less++] = pivot1;
1538 }
1539 }
1540 while (a[great] == pivot2) {
1541 great--;
1542 }
1543 for (int k = great - 1; k >= less; k--) {
1544 if (a[k] == pivot2) {
1545 a[k] = a[great];
1546 a[great--] = pivot2;
1547 }
1548 }
1549 }
1550
1551 // Sort center part recursively, excluding known pivot values
1552 sort(a, less, great);
1553 }
1554 }