1 /*
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * 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 2011.02.11 m765.827.12i:5\7pm
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 * The maximum number of runs in merge sort.
55 */
56 private static final int MAX_RUN_COUNT = 67;
57
58 /**
59 * The maximum length of run in merge sort.
60 */
61 private static final int MAX_RUN_LENGTH = 33;
62
63 /**
64 * If the length of an array to be sorted is less than this
65 * constant, Quicksort is used in preference to merge sort.
66 */
67 private static final int QUICKSORT_THRESHOLD = 286;
68
69 /**
70 * If the length of an array to be sorted is less than this
71 * constant, insertion sort is used in preference to Quicksort.
72 */
73 private static final int INSERTION_SORT_THRESHOLD = 47;
74
75 /**
76 * If the length of a byte array to be sorted is greater than this
77 * constant, counting sort is used in preference to insertion sort.
78 */
79 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
80
81 /**
82 * If the length of a short or char array to be sorted is greater
83 * than this constant, counting sort is used in preference to Quicksort.
84 */
85 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
86
87 /*
88 * Sorting methods for seven primitive types.
89 */
90
91 /**
92 * Sorts the specified array.
93 *
94 * @param a the array to be sorted
95 */
96 public static void sort(int[] a) {
97 sort(a, 0, a.length - 1);
98 }
99
100 /**
101 * Sorts the specified range of the array.
102 *
103 * @param a the array to be sorted
104 * @param left the index of the first element, inclusive, to be sorted
105 * @param right the index of the last element, inclusive, to be sorted
106 */
107 public static void sort(int[] a, int left, int right) {
108 // Use Quicksort on small arrays
109 if (right - left < QUICKSORT_THRESHOLD) {
110 sort(a, left, right, true);
111 return;
112 }
113
114 /*
115 * Index run[i] is the start of i-th run
116 * (ascending or descending sequence).
117 */
118 int[] run = new int[MAX_RUN_COUNT + 1];
119 int count = 0; run[0] = left;
120
121 // Check if the array is nearly sorted
122 for (int k = left; k < right; run[count] = k) {
123 if (a[k] < a[k + 1]) { // ascending
124 while (++k <= right && a[k - 1] <= a[k]);
125 } else if (a[k] > a[k + 1]) { // descending
126 while (++k <= right && a[k - 1] >= a[k]);
127 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
128 int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
129 }
130 } else { // equal
131 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
132 if (--m == 0) {
133 sort(a, left, right, true);
134 return;
135 }
136 }
137 }
138
139 /*
140 * The array is not highly structured,
141 * use Quicksort instead of merge sort.
142 */
143 if (++count == MAX_RUN_COUNT) {
144 sort(a, left, right, true);
145 return;
146 }
147 }
148
149 // Check special cases
150 if (run[count] == right++) { // The last run contains one element
151 run[++count] = right;
152 } else if (count == 1) { // The array is already sorted
153 return;
154 }
155
156 /*
157 * Create temporary array, which is used for merging.
158 * Implementation note: variable "right" is increased by 1.
159 */
160 int[] b; byte odd = 0;
161 for (int n = 1; (n <<= 1) < count; odd ^= 1);
162
163 if (odd == 0) {
164 b = a; a = new int[b.length];
165 for (int i = left - 1; ++i < right; a[i] = b[i]);
166 } else {
167 b = new int[a.length];
168 }
169
170 // Merging
171 for (int last; count > 1; count = last) {
172 for (int k = (last = 0) + 2; k <= count; k += 2) {
173 int hi = run[k], mi = run[k - 1];
174 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
175 if (q >= hi || p < mi && a[p] <= a[q]) {
176 b[i] = a[p++];
177 } else {
178 b[i] = a[q++];
179 }
180 }
181 run[++last] = hi;
182 }
183 if ((count & 1) != 0) {
184 for (int i = right, lo = run[count - 1]; --i >= lo;
185 b[i] = a[i]
186 );
187 run[++last] = right;
188 }
189 int[] t = a; a = b; b = t;
190 }
191 }
192
193 /**
194 * Sorts the specified range of the array by Dual-Pivot Quicksort.
195 *
196 * @param a the array to be sorted
197 * @param left the index of the first element, inclusive, to be sorted
198 * @param right the index of the last element, inclusive, to be sorted
199 * @param leftmost indicates if this part is the leftmost in the range
200 */
201 private static void sort(int[] a, int left, int right, boolean leftmost) {
202 int length = right - left + 1;
203
204 // Use insertion sort on tiny arrays
205 if (length < INSERTION_SORT_THRESHOLD) {
206 if (leftmost) {
207 /*
208 * Traditional (without sentinel) insertion sort,
209 * optimized for server VM, is used in case of
210 * the leftmost part.
211 */
212 for (int i = left, j = i; i < right; j = ++i) {
213 int ai = a[i + 1];
214 while (ai < a[j]) {
215 a[j + 1] = a[j];
216 if (j-- == left) {
217 break;
218 }
219 }
220 a[j + 1] = ai;
221 }
222 } else {
223 /*
224 * Skip the longest ascending sequence.
225 */
226 do {
227 if (left >= right) {
228 return;
229 }
230 } while (a[++left] >= a[left - 1]);
231
232 /*
233 * Every element from adjoining part plays the role
234 * of sentinel, therefore this allows us to avoid the
235 * left range check on each iteration. Moreover, we use
236 * the more optimized algorithm, so called pair insertion
237 * sort, which is faster (in the context of Quicksort)
238 * than traditional implementation of insertion sort.
239 */
240 for (int k = left; ++left <= right; k = ++left) {
241 int a1 = a[k], a2 = a[left];
242
243 if (a1 < a2) {
244 a2 = a1; a1 = a[left];
245 }
246 while (a1 < a[--k]) {
247 a[k + 2] = a[k];
248 }
249 a[++k + 1] = a1;
250
251 while (a2 < a[--k]) {
252 a[k + 1] = a[k];
253 }
254 a[k + 1] = a2;
255 }
256 int last = a[right];
257
258 while (last < a[--right]) {
259 a[right + 1] = a[right];
260 }
261 a[right + 1] = last;
262 }
263 return;
264 }
265
266 // Inexpensive approximation of length / 7
267 int seventh = (length >> 3) + (length >> 6) + 1;
268
269 /*
270 * Sort five evenly spaced elements around (and including) the
271 * center element in the range. These elements will be used for
272 * pivot selection as described below. The choice for spacing
273 * these elements was empirically determined to work well on
274 * a wide variety of inputs.
275 */
276 int e3 = (left + right) >>> 1; // The midpoint
277 int e2 = e3 - seventh;
278 int e1 = e2 - seventh;
279 int e4 = e3 + seventh;
280 int e5 = e4 + seventh;
281
282 // Sort these elements using insertion sort
283 if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
284
285 if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
286 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
287 }
288 if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
289 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
290 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
291 }
292 }
293 if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
294 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
295 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
296 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
297 }
298 }
299 }
300
301 // Pointers
302 int less = left; // The index of the first element of center part
303 int great = right; // The index before the first element of right part
304
305 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
306 /*
307 * Use the second and fourth of the five sorted elements as pivots.
308 * These values are inexpensive approximations of the first and
309 * second terciles of the array. Note that pivot1 <= pivot2.
310 */
311 int pivot1 = a[e2];
312 int pivot2 = a[e4];
313
314 /*
315 * The first and the last elements to be sorted are moved to the
316 * locations formerly occupied by the pivots. When partitioning
317 * is complete, the pivots are swapped back into their final
318 * positions, and excluded from subsequent sorting.
319 */
320 a[e2] = a[left];
321 a[e4] = a[right];
322
323 /*
324 * Skip elements, which are less or greater than pivot values.
325 */
326 while (a[++less] < pivot1);
327 while (a[--great] > pivot2);
328
329 /*
330 * Partitioning:
331 *
332 * left part center part right part
333 * +--------------------------------------------------------------+
334 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
335 * +--------------------------------------------------------------+
336 * ^ ^ ^
337 * | | |
338 * less k great
339 *
340 * Invariants:
341 *
342 * all in (left, less) < pivot1
343 * pivot1 <= all in [less, k) <= pivot2
344 * all in (great, right) > pivot2
345 *
346 * Pointer k is the first index of ?-part.
347 */
348 outer:
349 for (int k = less - 1; ++k <= great; ) {
350 int ak = a[k];
351 if (ak < pivot1) { // Move a[k] to left part
352 a[k] = a[less];
353 /*
354 * Here and below we use "a[i] = b; i++;" instead
355 * of "a[i++] = b;" due to performance issue.
356 */
357 a[less] = ak;
358 ++less;
359 } else if (ak > pivot2) { // Move a[k] to right part
360 while (a[great] > pivot2) {
361 if (great-- == k) {
362 break outer;
363 }
364 }
365 if (a[great] < pivot1) { // a[great] <= pivot2
366 a[k] = a[less];
367 a[less] = a[great];
368 ++less;
369 } else { // pivot1 <= a[great] <= pivot2
370 a[k] = a[great];
371 }
372 /*
373 * Here and below we use "a[i] = b; i--;" instead
374 * of "a[i--] = b;" due to performance issue.
375 */
376 a[great] = ak;
377 --great;
378 }
379 }
380
381 // Swap pivots into their final positions
382 a[left] = a[less - 1]; a[less - 1] = pivot1;
383 a[right] = a[great + 1]; a[great + 1] = pivot2;
384
385 // Sort left and right parts recursively, excluding known pivots
386 sort(a, left, less - 2, leftmost);
387 sort(a, great + 2, right, false);
388
389 /*
390 * If center part is too large (comprises > 4/7 of the array),
391 * swap internal pivot values to ends.
392 */
393 if (less < e1 && e5 < great) {
394 /*
395 * Skip elements, which are equal to pivot values.
396 */
397 while (a[less] == pivot1) {
398 ++less;
399 }
400
401 while (a[great] == pivot2) {
402 --great;
403 }
404
405 /*
406 * Partitioning:
407 *
408 * left part center part right part
409 * +----------------------------------------------------------+
410 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
411 * +----------------------------------------------------------+
412 * ^ ^ ^
413 * | | |
414 * less k great
415 *
416 * Invariants:
417 *
418 * all in (*, less) == pivot1
419 * pivot1 < all in [less, k) < pivot2
420 * all in (great, *) == pivot2
421 *
422 * Pointer k is the first index of ?-part.
423 */
424 outer:
425 for (int k = less - 1; ++k <= great; ) {
426 int ak = a[k];
427 if (ak == pivot1) { // Move a[k] to left part
428 a[k] = a[less];
429 a[less] = ak;
430 ++less;
431 } else if (ak == pivot2) { // Move a[k] to right part
432 while (a[great] == pivot2) {
433 if (great-- == k) {
434 break outer;
435 }
436 }
437 if (a[great] == pivot1) { // a[great] < pivot2
438 a[k] = a[less];
439 /*
440 * Even though a[great] equals to pivot1, the
441 * assignment a[less] = pivot1 may be incorrect,
442 * if a[great] and pivot1 are floating-point zeros
443 * of different signs. Therefore in float and
444 * double sorting methods we have to use more
445 * accurate assignment a[less] = a[great].
446 */
447 a[less] = pivot1;
448 ++less;
449 } else { // pivot1 < a[great] < pivot2
450 a[k] = a[great];
451 }
452 a[great] = ak;
453 --great;
454 }
455 }
456 }
457
458 // Sort center part recursively
459 sort(a, less, great, false);
460
461 } else { // Partitioning with one pivot
462 /*
463 * Use the third of the five sorted elements as pivot.
464 * This value is inexpensive approximation of the median.
465 */
466 int pivot = a[e3];
467
468 /*
469 * Partitioning degenerates to the traditional 3-way
470 * (or "Dutch National Flag") schema:
471 *
472 * left part center part right part
473 * +-------------------------------------------------+
474 * | < pivot | == pivot | ? | > pivot |
475 * +-------------------------------------------------+
476 * ^ ^ ^
477 * | | |
478 * less k great
479 *
480 * Invariants:
481 *
482 * all in (left, less) < pivot
483 * all in [less, k) == pivot
484 * all in (great, right) > pivot
485 *
486 * Pointer k is the first index of ?-part.
487 */
488 for (int k = less; k <= great; ++k) {
489 if (a[k] == pivot) {
490 continue;
491 }
492 int ak = a[k];
493 if (ak < pivot) { // Move a[k] to left part
494 a[k] = a[less];
495 a[less] = ak;
496 ++less;
497 } else { // a[k] > pivot - Move a[k] to right part
498 while (a[great] > pivot) {
499 --great;
500 }
501 if (a[great] < pivot) { // a[great] <= pivot
502 a[k] = a[less];
503 a[less] = a[great];
504 ++less;
505 } else { // a[great] == pivot
506 /*
507 * Even though a[great] equals to pivot, the
508 * assignment a[k] = pivot may be incorrect,
509 * if a[great] and pivot are floating-point
510 * zeros of different signs. Therefore in float
511 * and double sorting methods we have to use
512 * more accurate assignment a[k] = a[great].
513 */
514 a[k] = pivot;
515 }
516 a[great] = ak;
517 --great;
518 }
519 }
520
521 /*
522 * Sort left and right parts recursively.
523 * All elements from center part are equal
524 * and, therefore, already sorted.
525 */
526 sort(a, left, less - 1, leftmost);
527 sort(a, great + 1, right, false);
528 }
529 }
530
531 /**
532 * Sorts the specified array.
533 *
534 * @param a the array to be sorted
535 */
536 public static void sort(long[] a) {
537 sort(a, 0, a.length - 1);
538 }
539
540 /**
541 * Sorts the specified range of the array.
542 *
543 * @param a the array to be sorted
544 * @param left the index of the first element, inclusive, to be sorted
545 * @param right the index of the last element, inclusive, to be sorted
546 */
547 public static void sort(long[] a, int left, int right) {
548 // Use Quicksort on small arrays
549 if (right - left < QUICKSORT_THRESHOLD) {
550 sort(a, left, right, true);
551 return;
552 }
553
554 /*
555 * Index run[i] is the start of i-th run
556 * (ascending or descending sequence).
557 */
558 int[] run = new int[MAX_RUN_COUNT + 1];
559 int count = 0; run[0] = left;
560
561 // Check if the array is nearly sorted
562 for (int k = left; k < right; run[count] = k) {
563 if (a[k] < a[k + 1]) { // ascending
564 while (++k <= right && a[k - 1] <= a[k]);
565 } else if (a[k] > a[k + 1]) { // descending
566 while (++k <= right && a[k - 1] >= a[k]);
567 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
568 long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
569 }
570 } else { // equal
571 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
572 if (--m == 0) {
573 sort(a, left, right, true);
574 return;
575 }
576 }
577 }
578
579 /*
580 * The array is not highly structured,
581 * use Quicksort instead of merge sort.
582 */
583 if (++count == MAX_RUN_COUNT) {
584 sort(a, left, right, true);
585 return;
586 }
587 }
588
589 // Check special cases
590 if (run[count] == right++) { // The last run contains one element
591 run[++count] = right;
592 } else if (count == 1) { // The array is already sorted
593 return;
594 }
595
596 /*
597 * Create temporary array, which is used for merging.
598 * Implementation note: variable "right" is increased by 1.
599 */
600 long[] b; byte odd = 0;
601 for (int n = 1; (n <<= 1) < count; odd ^= 1);
602
603 if (odd == 0) {
604 b = a; a = new long[b.length];
605 for (int i = left - 1; ++i < right; a[i] = b[i]);
606 } else {
607 b = new long[a.length];
608 }
609
610 // Merging
611 for (int last; count > 1; count = last) {
612 for (int k = (last = 0) + 2; k <= count; k += 2) {
613 int hi = run[k], mi = run[k - 1];
614 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
615 if (q >= hi || p < mi && a[p] <= a[q]) {
616 b[i] = a[p++];
617 } else {
618 b[i] = a[q++];
619 }
620 }
621 run[++last] = hi;
622 }
623 if ((count & 1) != 0) {
624 for (int i = right, lo = run[count - 1]; --i >= lo;
625 b[i] = a[i]
626 );
627 run[++last] = right;
628 }
629 long[] t = a; a = b; b = t;
630 }
631 }
632
633 /**
634 * Sorts the specified range of the array by Dual-Pivot Quicksort.
635 *
636 * @param a the array to be sorted
637 * @param left the index of the first element, inclusive, to be sorted
638 * @param right the index of the last element, inclusive, to be sorted
639 * @param leftmost indicates if this part is the leftmost in the range
640 */
641 private static void sort(long[] a, int left, int right, boolean leftmost) {
642 int length = right - left + 1;
643
644 // Use insertion sort on tiny arrays
645 if (length < INSERTION_SORT_THRESHOLD) {
646 if (leftmost) {
647 /*
648 * Traditional (without sentinel) insertion sort,
649 * optimized for server VM, is used in case of
650 * the leftmost part.
651 */
652 for (int i = left, j = i; i < right; j = ++i) {
653 long ai = a[i + 1];
654 while (ai < a[j]) {
655 a[j + 1] = a[j];
656 if (j-- == left) {
657 break;
658 }
659 }
660 a[j + 1] = ai;
661 }
662 } else {
663 /*
664 * Skip the longest ascending sequence.
665 */
666 do {
667 if (left >= right) {
668 return;
669 }
670 } while (a[++left] >= a[left - 1]);
671
672 /*
673 * Every element from adjoining part plays the role
674 * of sentinel, therefore this allows us to avoid the
675 * left range check on each iteration. Moreover, we use
676 * the more optimized algorithm, so called pair insertion
677 * sort, which is faster (in the context of Quicksort)
678 * than traditional implementation of insertion sort.
679 */
680 for (int k = left; ++left <= right; k = ++left) {
681 long a1 = a[k], a2 = a[left];
682
683 if (a1 < a2) {
684 a2 = a1; a1 = a[left];
685 }
686 while (a1 < a[--k]) {
687 a[k + 2] = a[k];
688 }
689 a[++k + 1] = a1;
690
691 while (a2 < a[--k]) {
692 a[k + 1] = a[k];
693 }
694 a[k + 1] = a2;
695 }
696 long last = a[right];
697
698 while (last < a[--right]) {
699 a[right + 1] = a[right];
700 }
701 a[right + 1] = last;
702 }
703 return;
704 }
705
706 // Inexpensive approximation of length / 7
707 int seventh = (length >> 3) + (length >> 6) + 1;
708
709 /*
710 * Sort five evenly spaced elements around (and including) the
711 * center element in the range. These elements will be used for
712 * pivot selection as described below. The choice for spacing
713 * these elements was empirically determined to work well on
714 * a wide variety of inputs.
715 */
716 int e3 = (left + right) >>> 1; // The midpoint
717 int e2 = e3 - seventh;
718 int e1 = e2 - seventh;
719 int e4 = e3 + seventh;
720 int e5 = e4 + seventh;
721
722 // Sort these elements using insertion sort
723 if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
724
725 if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
726 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
727 }
728 if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
729 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
730 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
731 }
732 }
733 if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
734 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
735 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
736 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
737 }
738 }
739 }
740
741 // Pointers
742 int less = left; // The index of the first element of center part
743 int great = right; // The index before the first element of right part
744
745 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
746 /*
747 * Use the second and fourth of the five sorted elements as pivots.
748 * These values are inexpensive approximations of the first and
749 * second terciles of the array. Note that pivot1 <= pivot2.
750 */
751 long pivot1 = a[e2];
752 long pivot2 = a[e4];
753
754 /*
755 * The first and the last elements to be sorted are moved to the
756 * locations formerly occupied by the pivots. When partitioning
757 * is complete, the pivots are swapped back into their final
758 * positions, and excluded from subsequent sorting.
759 */
760 a[e2] = a[left];
761 a[e4] = a[right];
762
763 /*
764 * Skip elements, which are less or greater than pivot values.
765 */
766 while (a[++less] < pivot1);
767 while (a[--great] > pivot2);
768
769 /*
770 * Partitioning:
771 *
772 * left part center part right part
773 * +--------------------------------------------------------------+
774 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
775 * +--------------------------------------------------------------+
776 * ^ ^ ^
777 * | | |
778 * less k great
779 *
780 * Invariants:
781 *
782 * all in (left, less) < pivot1
783 * pivot1 <= all in [less, k) <= pivot2
784 * all in (great, right) > pivot2
785 *
786 * Pointer k is the first index of ?-part.
787 */
788 outer:
789 for (int k = less - 1; ++k <= great; ) {
790 long ak = a[k];
791 if (ak < pivot1) { // Move a[k] to left part
792 a[k] = a[less];
793 /*
794 * Here and below we use "a[i] = b; i++;" instead
795 * of "a[i++] = b;" due to performance issue.
796 */
797 a[less] = ak;
798 ++less;
799 } else if (ak > pivot2) { // Move a[k] to right part
800 while (a[great] > pivot2) {
801 if (great-- == k) {
802 break outer;
803 }
804 }
805 if (a[great] < pivot1) { // a[great] <= pivot2
806 a[k] = a[less];
807 a[less] = a[great];
808 ++less;
809 } else { // pivot1 <= a[great] <= pivot2
810 a[k] = a[great];
811 }
812 /*
813 * Here and below we use "a[i] = b; i--;" instead
814 * of "a[i--] = b;" due to performance issue.
815 */
816 a[great] = ak;
817 --great;
818 }
819 }
820
821 // Swap pivots into their final positions
822 a[left] = a[less - 1]; a[less - 1] = pivot1;
823 a[right] = a[great + 1]; a[great + 1] = pivot2;
824
825 // Sort left and right parts recursively, excluding known pivots
826 sort(a, left, less - 2, leftmost);
827 sort(a, great + 2, right, false);
828
829 /*
830 * If center part is too large (comprises > 4/7 of the array),
831 * swap internal pivot values to ends.
832 */
833 if (less < e1 && e5 < great) {
834 /*
835 * Skip elements, which are equal to pivot values.
836 */
837 while (a[less] == pivot1) {
838 ++less;
839 }
840
841 while (a[great] == pivot2) {
842 --great;
843 }
844
845 /*
846 * Partitioning:
847 *
848 * left part center part right part
849 * +----------------------------------------------------------+
850 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
851 * +----------------------------------------------------------+
852 * ^ ^ ^
853 * | | |
854 * less k great
855 *
856 * Invariants:
857 *
858 * all in (*, less) == pivot1
859 * pivot1 < all in [less, k) < pivot2
860 * all in (great, *) == pivot2
861 *
862 * Pointer k is the first index of ?-part.
863 */
864 outer:
865 for (int k = less - 1; ++k <= great; ) {
866 long ak = a[k];
867 if (ak == pivot1) { // Move a[k] to left part
868 a[k] = a[less];
869 a[less] = ak;
870 ++less;
871 } else if (ak == pivot2) { // Move a[k] to right part
872 while (a[great] == pivot2) {
873 if (great-- == k) {
874 break outer;
875 }
876 }
877 if (a[great] == pivot1) { // a[great] < pivot2
878 a[k] = a[less];
879 /*
880 * Even though a[great] equals to pivot1, the
881 * assignment a[less] = pivot1 may be incorrect,
882 * if a[great] and pivot1 are floating-point zeros
883 * of different signs. Therefore in float and
884 * double sorting methods we have to use more
885 * accurate assignment a[less] = a[great].
886 */
887 a[less] = pivot1;
888 ++less;
889 } else { // pivot1 < a[great] < pivot2
890 a[k] = a[great];
891 }
892 a[great] = ak;
893 --great;
894 }
895 }
896 }
897
898 // Sort center part recursively
899 sort(a, less, great, false);
900
901 } else { // Partitioning with one pivot
902 /*
903 * Use the third of the five sorted elements as pivot.
904 * This value is inexpensive approximation of the median.
905 */
906 long pivot = a[e3];
907
908 /*
909 * Partitioning degenerates to the traditional 3-way
910 * (or "Dutch National Flag") schema:
911 *
912 * left part center part right part
913 * +-------------------------------------------------+
914 * | < pivot | == pivot | ? | > pivot |
915 * +-------------------------------------------------+
916 * ^ ^ ^
917 * | | |
918 * less k great
919 *
920 * Invariants:
921 *
922 * all in (left, less) < pivot
923 * all in [less, k) == pivot
924 * all in (great, right) > pivot
925 *
926 * Pointer k is the first index of ?-part.
927 */
928 for (int k = less; k <= great; ++k) {
929 if (a[k] == pivot) {
930 continue;
931 }
932 long ak = a[k];
933 if (ak < pivot) { // Move a[k] to left part
934 a[k] = a[less];
935 a[less] = ak;
936 ++less;
937 } else { // a[k] > pivot - Move a[k] to right part
938 while (a[great] > pivot) {
939 --great;
940 }
941 if (a[great] < pivot) { // a[great] <= pivot
942 a[k] = a[less];
943 a[less] = a[great];
944 ++less;
945 } else { // a[great] == pivot
946 /*
947 * Even though a[great] equals to pivot, the
948 * assignment a[k] = pivot may be incorrect,
949 * if a[great] and pivot are floating-point
950 * zeros of different signs. Therefore in float
951 * and double sorting methods we have to use
952 * more accurate assignment a[k] = a[great].
953 */
954 a[k] = pivot;
955 }
956 a[great] = ak;
957 --great;
958 }
959 }
960
961 /*
962 * Sort left and right parts recursively.
963 * All elements from center part are equal
964 * and, therefore, already sorted.
965 */
966 sort(a, left, less - 1, leftmost);
967 sort(a, great + 1, right, false);
968 }
969 }
970
971 /**
972 * Sorts the specified array.
973 *
974 * @param a the array to be sorted
975 */
976 public static void sort(short[] a) {
977 sort(a, 0, a.length - 1);
978 }
979
980 /**
981 * Sorts the specified range of the array.
982 *
983 * @param a the array to be sorted
984 * @param left the index of the first element, inclusive, to be sorted
985 * @param right the index of the last element, inclusive, to be sorted
986 */
987 public static void sort(short[] a, int left, int right) {
988 // Use counting sort on large arrays
989 if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
990 int[] count = new int[NUM_SHORT_VALUES];
991
992 for (int i = left - 1; ++i <= right;
993 count[a[i] - Short.MIN_VALUE]++
994 );
995 for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
996 while (count[--i] == 0);
997 short value = (short) (i + Short.MIN_VALUE);
998 int s = count[i];
999
1000 do {
1001 a[--k] = value;
1002 } while (--s > 0);
1003 }
1004 } else { // Use Dual-Pivot Quicksort on small arrays
1005 doSort(a, left, right);
1006 }
1007 }
1008
1009 /** The number of distinct short values. */
1010 private static final int NUM_SHORT_VALUES = 1 << 16;
1011
1012 /**
1013 * Sorts the specified range of the array.
1014 *
1015 * @param a the array to be sorted
1016 * @param left the index of the first element, inclusive, to be sorted
1017 * @param right the index of the last element, inclusive, to be sorted
1018 */
1019 private static void doSort(short[] a, int left, int right) {
1020 // Use Quicksort on small arrays
1021 if (right - left < QUICKSORT_THRESHOLD) {
1022 sort(a, left, right, true);
1023 return;
1024 }
1025
1026 /*
1027 * Index run[i] is the start of i-th run
1028 * (ascending or descending sequence).
1029 */
1030 int[] run = new int[MAX_RUN_COUNT + 1];
1031 int count = 0; run[0] = left;
1032
1033 // Check if the array is nearly sorted
1034 for (int k = left; k < right; run[count] = k) {
1035 if (a[k] < a[k + 1]) { // ascending
1036 while (++k <= right && a[k - 1] <= a[k]);
1037 } else if (a[k] > a[k + 1]) { // descending
1038 while (++k <= right && a[k - 1] >= a[k]);
1039 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1040 short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1041 }
1042 } else { // equal
1043 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1044 if (--m == 0) {
1045 sort(a, left, right, true);
1046 return;
1047 }
1048 }
1049 }
1050
1051 /*
1052 * The array is not highly structured,
1053 * use Quicksort instead of merge sort.
1054 */
1055 if (++count == MAX_RUN_COUNT) {
1056 sort(a, left, right, true);
1057 return;
1058 }
1059 }
1060
1061 // Check special cases
1062 if (run[count] == right++) { // The last run contains one element
1063 run[++count] = right;
1064 } else if (count == 1) { // The array is already sorted
1065 return;
1066 }
1067
1068 /*
1069 * Create temporary array, which is used for merging.
1070 * Implementation note: variable "right" is increased by 1.
1071 */
1072 short[] b; byte odd = 0;
1073 for (int n = 1; (n <<= 1) < count; odd ^= 1);
1074
1075 if (odd == 0) {
1076 b = a; a = new short[b.length];
1077 for (int i = left - 1; ++i < right; a[i] = b[i]);
1078 } else {
1079 b = new short[a.length];
1080 }
1081
1082 // Merging
1083 for (int last; count > 1; count = last) {
1084 for (int k = (last = 0) + 2; k <= count; k += 2) {
1085 int hi = run[k], mi = run[k - 1];
1086 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1087 if (q >= hi || p < mi && a[p] <= a[q]) {
1088 b[i] = a[p++];
1089 } else {
1090 b[i] = a[q++];
1091 }
1092 }
1093 run[++last] = hi;
1094 }
1095 if ((count & 1) != 0) {
1096 for (int i = right, lo = run[count - 1]; --i >= lo;
1097 b[i] = a[i]
1098 );
1099 run[++last] = right;
1100 }
1101 short[] t = a; a = b; b = t;
1102 }
1103 }
1104
1105 /**
1106 * Sorts the specified range of the array by Dual-Pivot Quicksort.
1107 *
1108 * @param a the array to be sorted
1109 * @param left the index of the first element, inclusive, to be sorted
1110 * @param right the index of the last element, inclusive, to be sorted
1111 * @param leftmost indicates if this part is the leftmost in the range
1112 */
1113 private static void sort(short[] a, int left, int right, boolean leftmost) {
1114 int length = right - left + 1;
1115
1116 // Use insertion sort on tiny arrays
1117 if (length < INSERTION_SORT_THRESHOLD) {
1118 if (leftmost) {
1119 /*
1120 * Traditional (without sentinel) insertion sort,
1121 * optimized for server VM, is used in case of
1122 * the leftmost part.
1123 */
1124 for (int i = left, j = i; i < right; j = ++i) {
1125 short ai = a[i + 1];
1126 while (ai < a[j]) {
1127 a[j + 1] = a[j];
1128 if (j-- == left) {
1129 break;
1130 }
1131 }
1132 a[j + 1] = ai;
1133 }
1134 } else {
1135 /*
1136 * Skip the longest ascending sequence.
1137 */
1138 do {
1139 if (left >= right) {
1140 return;
1141 }
1142 } while (a[++left] >= a[left - 1]);
1143
1144 /*
1145 * Every element from adjoining part plays the role
1146 * of sentinel, therefore this allows us to avoid the
1147 * left range check on each iteration. Moreover, we use
1148 * the more optimized algorithm, so called pair insertion
1149 * sort, which is faster (in the context of Quicksort)
1150 * than traditional implementation of insertion sort.
1151 */
1152 for (int k = left; ++left <= right; k = ++left) {
1153 short a1 = a[k], a2 = a[left];
1154
1155 if (a1 < a2) {
1156 a2 = a1; a1 = a[left];
1157 }
1158 while (a1 < a[--k]) {
1159 a[k + 2] = a[k];
1160 }
1161 a[++k + 1] = a1;
1162
1163 while (a2 < a[--k]) {
1164 a[k + 1] = a[k];
1165 }
1166 a[k + 1] = a2;
1167 }
1168 short last = a[right];
1169
1170 while (last < a[--right]) {
1171 a[right + 1] = a[right];
1172 }
1173 a[right + 1] = last;
1174 }
1175 return;
1176 }
1177
1178 // Inexpensive approximation of length / 7
1179 int seventh = (length >> 3) + (length >> 6) + 1;
1180
1181 /*
1182 * Sort five evenly spaced elements around (and including) the
1183 * center element in the range. These elements will be used for
1184 * pivot selection as described below. The choice for spacing
1185 * these elements was empirically determined to work well on
1186 * a wide variety of inputs.
1187 */
1188 int e3 = (left + right) >>> 1; // The midpoint
1189 int e2 = e3 - seventh;
1190 int e1 = e2 - seventh;
1191 int e4 = e3 + seventh;
1192 int e5 = e4 + seventh;
1193
1194 // Sort these elements using insertion sort
1195 if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1196
1197 if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1198 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1199 }
1200 if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1201 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1202 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1203 }
1204 }
1205 if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1206 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1207 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1208 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1209 }
1210 }
1211 }
1212
1213 // Pointers
1214 int less = left; // The index of the first element of center part
1215 int great = right; // The index before the first element of right part
1216
1217 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1218 /*
1219 * Use the second and fourth of the five sorted elements as pivots.
1220 * These values are inexpensive approximations of the first and
1221 * second terciles of the array. Note that pivot1 <= pivot2.
1222 */
1223 short pivot1 = a[e2];
1224 short pivot2 = a[e4];
1225
1226 /*
1227 * The first and the last elements to be sorted are moved to the
1228 * locations formerly occupied by the pivots. When partitioning
1229 * is complete, the pivots are swapped back into their final
1230 * positions, and excluded from subsequent sorting.
1231 */
1232 a[e2] = a[left];
1233 a[e4] = a[right];
1234
1235 /*
1236 * Skip elements, which are less or greater than pivot values.
1237 */
1238 while (a[++less] < pivot1);
1239 while (a[--great] > pivot2);
1240
1241 /*
1242 * Partitioning:
1243 *
1244 * left part center part right part
1245 * +--------------------------------------------------------------+
1246 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1247 * +--------------------------------------------------------------+
1248 * ^ ^ ^
1249 * | | |
1250 * less k great
1251 *
1252 * Invariants:
1253 *
1254 * all in (left, less) < pivot1
1255 * pivot1 <= all in [less, k) <= pivot2
1256 * all in (great, right) > pivot2
1257 *
1258 * Pointer k is the first index of ?-part.
1259 */
1260 outer:
1261 for (int k = less - 1; ++k <= great; ) {
1262 short ak = a[k];
1263 if (ak < pivot1) { // Move a[k] to left part
1264 a[k] = a[less];
1265 /*
1266 * Here and below we use "a[i] = b; i++;" instead
1267 * of "a[i++] = b;" due to performance issue.
1268 */
1269 a[less] = ak;
1270 ++less;
1271 } else if (ak > pivot2) { // Move a[k] to right part
1272 while (a[great] > pivot2) {
1273 if (great-- == k) {
1274 break outer;
1275 }
1276 }
1277 if (a[great] < pivot1) { // a[great] <= pivot2
1278 a[k] = a[less];
1279 a[less] = a[great];
1280 ++less;
1281 } else { // pivot1 <= a[great] <= pivot2
1282 a[k] = a[great];
1283 }
1284 /*
1285 * Here and below we use "a[i] = b; i--;" instead
1286 * of "a[i--] = b;" due to performance issue.
1287 */
1288 a[great] = ak;
1289 --great;
1290 }
1291 }
1292
1293 // Swap pivots into their final positions
1294 a[left] = a[less - 1]; a[less - 1] = pivot1;
1295 a[right] = a[great + 1]; a[great + 1] = pivot2;
1296
1297 // Sort left and right parts recursively, excluding known pivots
1298 sort(a, left, less - 2, leftmost);
1299 sort(a, great + 2, right, false);
1300
1301 /*
1302 * If center part is too large (comprises > 4/7 of the array),
1303 * swap internal pivot values to ends.
1304 */
1305 if (less < e1 && e5 < great) {
1306 /*
1307 * Skip elements, which are equal to pivot values.
1308 */
1309 while (a[less] == pivot1) {
1310 ++less;
1311 }
1312
1313 while (a[great] == pivot2) {
1314 --great;
1315 }
1316
1317 /*
1318 * Partitioning:
1319 *
1320 * left part center part right part
1321 * +----------------------------------------------------------+
1322 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1323 * +----------------------------------------------------------+
1324 * ^ ^ ^
1325 * | | |
1326 * less k great
1327 *
1328 * Invariants:
1329 *
1330 * all in (*, less) == pivot1
1331 * pivot1 < all in [less, k) < pivot2
1332 * all in (great, *) == pivot2
1333 *
1334 * Pointer k is the first index of ?-part.
1335 */
1336 outer:
1337 for (int k = less - 1; ++k <= great; ) {
1338 short ak = a[k];
1339 if (ak == pivot1) { // Move a[k] to left part
1340 a[k] = a[less];
1341 a[less] = ak;
1342 ++less;
1343 } else if (ak == pivot2) { // Move a[k] to right part
1344 while (a[great] == pivot2) {
1345 if (great-- == k) {
1346 break outer;
1347 }
1348 }
1349 if (a[great] == pivot1) { // a[great] < pivot2
1350 a[k] = a[less];
1351 /*
1352 * Even though a[great] equals to pivot1, the
1353 * assignment a[less] = pivot1 may be incorrect,
1354 * if a[great] and pivot1 are floating-point zeros
1355 * of different signs. Therefore in float and
1356 * double sorting methods we have to use more
1357 * accurate assignment a[less] = a[great].
1358 */
1359 a[less] = pivot1;
1360 ++less;
1361 } else { // pivot1 < a[great] < pivot2
1362 a[k] = a[great];
1363 }
1364 a[great] = ak;
1365 --great;
1366 }
1367 }
1368 }
1369
1370 // Sort center part recursively
1371 sort(a, less, great, false);
1372
1373 } else { // Partitioning with one pivot
1374 /*
1375 * Use the third of the five sorted elements as pivot.
1376 * This value is inexpensive approximation of the median.
1377 */
1378 short pivot = a[e3];
1379
1380 /*
1381 * Partitioning degenerates to the traditional 3-way
1382 * (or "Dutch National Flag") schema:
1383 *
1384 * left part center part right part
1385 * +-------------------------------------------------+
1386 * | < pivot | == pivot | ? | > pivot |
1387 * +-------------------------------------------------+
1388 * ^ ^ ^
1389 * | | |
1390 * less k great
1391 *
1392 * Invariants:
1393 *
1394 * all in (left, less) < pivot
1395 * all in [less, k) == pivot
1396 * all in (great, right) > pivot
1397 *
1398 * Pointer k is the first index of ?-part.
1399 */
1400 for (int k = less; k <= great; ++k) {
1401 if (a[k] == pivot) {
1402 continue;
1403 }
1404 short ak = a[k];
1405 if (ak < pivot) { // Move a[k] to left part
1406 a[k] = a[less];
1407 a[less] = ak;
1408 ++less;
1409 } else { // a[k] > pivot - Move a[k] to right part
1410 while (a[great] > pivot) {
1411 --great;
1412 }
1413 if (a[great] < pivot) { // a[great] <= pivot
1414 a[k] = a[less];
1415 a[less] = a[great];
1416 ++less;
1417 } else { // a[great] == pivot
1418 /*
1419 * Even though a[great] equals to pivot, the
1420 * assignment a[k] = pivot may be incorrect,
1421 * if a[great] and pivot are floating-point
1422 * zeros of different signs. Therefore in float
1423 * and double sorting methods we have to use
1424 * more accurate assignment a[k] = a[great].
1425 */
1426 a[k] = pivot;
1427 }
1428 a[great] = ak;
1429 --great;
1430 }
1431 }
1432
1433 /*
1434 * Sort left and right parts recursively.
1435 * All elements from center part are equal
1436 * and, therefore, already sorted.
1437 */
1438 sort(a, left, less - 1, leftmost);
1439 sort(a, great + 1, right, false);
1440 }
1441 }
1442
1443 /**
1444 * Sorts the specified array.
1445 *
1446 * @param a the array to be sorted
1447 */
1448 public static void sort(char[] a) {
1449 sort(a, 0, a.length - 1);
1450 }
1451
1452 /**
1453 * Sorts the specified range of the array.
1454 *
1455 * @param a the array to be sorted
1456 * @param left the index of the first element, inclusive, to be sorted
1457 * @param right the index of the last element, inclusive, to be sorted
1458 */
1459 public static void sort(char[] a, int left, int right) {
1460 // Use counting sort on large arrays
1461 if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
1462 int[] count = new int[NUM_CHAR_VALUES];
1463
1464 for (int i = left - 1; ++i <= right;
1465 count[a[i]]++
1466 );
1467 for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
1468 while (count[--i] == 0);
1469 char value = (char) i;
1470 int s = count[i];
1471
1472 do {
1473 a[--k] = value;
1474 } while (--s > 0);
1475 }
1476 } else { // Use Dual-Pivot Quicksort on small arrays
1477 doSort(a, left, right);
1478 }
1479 }
1480
1481 /** The number of distinct char values. */
1482 private static final int NUM_CHAR_VALUES = 1 << 16;
1483
1484 /**
1485 * Sorts the specified range of the array.
1486 *
1487 * @param a the array to be sorted
1488 * @param left the index of the first element, inclusive, to be sorted
1489 * @param right the index of the last element, inclusive, to be sorted
1490 */
1491 private static void doSort(char[] a, int left, int right) {
1492 // Use Quicksort on small arrays
1493 if (right - left < QUICKSORT_THRESHOLD) {
1494 sort(a, left, right, true);
1495 return;
1496 }
1497
1498 /*
1499 * Index run[i] is the start of i-th run
1500 * (ascending or descending sequence).
1501 */
1502 int[] run = new int[MAX_RUN_COUNT + 1];
1503 int count = 0; run[0] = left;
1504
1505 // Check if the array is nearly sorted
1506 for (int k = left; k < right; run[count] = k) {
1507 if (a[k] < a[k + 1]) { // ascending
1508 while (++k <= right && a[k - 1] <= a[k]);
1509 } else if (a[k] > a[k + 1]) { // descending
1510 while (++k <= right && a[k - 1] >= a[k]);
1511 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1512 char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1513 }
1514 } else { // equal
1515 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1516 if (--m == 0) {
1517 sort(a, left, right, true);
1518 return;
1519 }
1520 }
1521 }
1522
1523 /*
1524 * The array is not highly structured,
1525 * use Quicksort instead of merge sort.
1526 */
1527 if (++count == MAX_RUN_COUNT) {
1528 sort(a, left, right, true);
1529 return;
1530 }
1531 }
1532
1533 // Check special cases
1534 if (run[count] == right++) { // The last run contains one element
1535 run[++count] = right;
1536 } else if (count == 1) { // The array is already sorted
1537 return;
1538 }
1539
1540 /*
1541 * Create temporary array, which is used for merging.
1542 * Implementation note: variable "right" is increased by 1.
1543 */
1544 char[] b; byte odd = 0;
1545 for (int n = 1; (n <<= 1) < count; odd ^= 1);
1546
1547 if (odd == 0) {
1548 b = a; a = new char[b.length];
1549 for (int i = left - 1; ++i < right; a[i] = b[i]);
1550 } else {
1551 b = new char[a.length];
1552 }
1553
1554 // Merging
1555 for (int last; count > 1; count = last) {
1556 for (int k = (last = 0) + 2; k <= count; k += 2) {
1557 int hi = run[k], mi = run[k - 1];
1558 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1559 if (q >= hi || p < mi && a[p] <= a[q]) {
1560 b[i] = a[p++];
1561 } else {
1562 b[i] = a[q++];
1563 }
1564 }
1565 run[++last] = hi;
1566 }
1567 if ((count & 1) != 0) {
1568 for (int i = right, lo = run[count - 1]; --i >= lo;
1569 b[i] = a[i]
1570 );
1571 run[++last] = right;
1572 }
1573 char[] t = a; a = b; b = t;
1574 }
1575 }
1576
1577 /**
1578 * Sorts the specified range of the array by Dual-Pivot Quicksort.
1579 *
1580 * @param a the array to be sorted
1581 * @param left the index of the first element, inclusive, to be sorted
1582 * @param right the index of the last element, inclusive, to be sorted
1583 * @param leftmost indicates if this part is the leftmost in the range
1584 */
1585 private static void sort(char[] a, int left, int right, boolean leftmost) {
1586 int length = right - left + 1;
1587
1588 // Use insertion sort on tiny arrays
1589 if (length < INSERTION_SORT_THRESHOLD) {
1590 if (leftmost) {
1591 /*
1592 * Traditional (without sentinel) insertion sort,
1593 * optimized for server VM, is used in case of
1594 * the leftmost part.
1595 */
1596 for (int i = left, j = i; i < right; j = ++i) {
1597 char ai = a[i + 1];
1598 while (ai < a[j]) {
1599 a[j + 1] = a[j];
1600 if (j-- == left) {
1601 break;
1602 }
1603 }
1604 a[j + 1] = ai;
1605 }
1606 } else {
1607 /*
1608 * Skip the longest ascending sequence.
1609 */
1610 do {
1611 if (left >= right) {
1612 return;
1613 }
1614 } while (a[++left] >= a[left - 1]);
1615
1616 /*
1617 * Every element from adjoining part plays the role
1618 * of sentinel, therefore this allows us to avoid the
1619 * left range check on each iteration. Moreover, we use
1620 * the more optimized algorithm, so called pair insertion
1621 * sort, which is faster (in the context of Quicksort)
1622 * than traditional implementation of insertion sort.
1623 */
1624 for (int k = left; ++left <= right; k = ++left) {
1625 char a1 = a[k], a2 = a[left];
1626
1627 if (a1 < a2) {
1628 a2 = a1; a1 = a[left];
1629 }
1630 while (a1 < a[--k]) {
1631 a[k + 2] = a[k];
1632 }
1633 a[++k + 1] = a1;
1634
1635 while (a2 < a[--k]) {
1636 a[k + 1] = a[k];
1637 }
1638 a[k + 1] = a2;
1639 }
1640 char last = a[right];
1641
1642 while (last < a[--right]) {
1643 a[right + 1] = a[right];
1644 }
1645 a[right + 1] = last;
1646 }
1647 return;
1648 }
1649
1650 // Inexpensive approximation of length / 7
1651 int seventh = (length >> 3) + (length >> 6) + 1;
1652
1653 /*
1654 * Sort five evenly spaced elements around (and including) the
1655 * center element in the range. These elements will be used for
1656 * pivot selection as described below. The choice for spacing
1657 * these elements was empirically determined to work well on
1658 * a wide variety of inputs.
1659 */
1660 int e3 = (left + right) >>> 1; // The midpoint
1661 int e2 = e3 - seventh;
1662 int e1 = e2 - seventh;
1663 int e4 = e3 + seventh;
1664 int e5 = e4 + seventh;
1665
1666 // Sort these elements using insertion sort
1667 if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1668
1669 if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1670 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1671 }
1672 if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1673 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1674 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1675 }
1676 }
1677 if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1678 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1679 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1680 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1681 }
1682 }
1683 }
1684
1685 // Pointers
1686 int less = left; // The index of the first element of center part
1687 int great = right; // The index before the first element of right part
1688
1689 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1690 /*
1691 * Use the second and fourth of the five sorted elements as pivots.
1692 * These values are inexpensive approximations of the first and
1693 * second terciles of the array. Note that pivot1 <= pivot2.
1694 */
1695 char pivot1 = a[e2];
1696 char pivot2 = a[e4];
1697
1698 /*
1699 * The first and the last elements to be sorted are moved to the
1700 * locations formerly occupied by the pivots. When partitioning
1701 * is complete, the pivots are swapped back into their final
1702 * positions, and excluded from subsequent sorting.
1703 */
1704 a[e2] = a[left];
1705 a[e4] = a[right];
1706
1707 /*
1708 * Skip elements, which are less or greater than pivot values.
1709 */
1710 while (a[++less] < pivot1);
1711 while (a[--great] > pivot2);
1712
1713 /*
1714 * Partitioning:
1715 *
1716 * left part center part right part
1717 * +--------------------------------------------------------------+
1718 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1719 * +--------------------------------------------------------------+
1720 * ^ ^ ^
1721 * | | |
1722 * less k great
1723 *
1724 * Invariants:
1725 *
1726 * all in (left, less) < pivot1
1727 * pivot1 <= all in [less, k) <= pivot2
1728 * all in (great, right) > pivot2
1729 *
1730 * Pointer k is the first index of ?-part.
1731 */
1732 outer:
1733 for (int k = less - 1; ++k <= great; ) {
1734 char ak = a[k];
1735 if (ak < pivot1) { // Move a[k] to left part
1736 a[k] = a[less];
1737 /*
1738 * Here and below we use "a[i] = b; i++;" instead
1739 * of "a[i++] = b;" due to performance issue.
1740 */
1741 a[less] = ak;
1742 ++less;
1743 } else if (ak > pivot2) { // Move a[k] to right part
1744 while (a[great] > pivot2) {
1745 if (great-- == k) {
1746 break outer;
1747 }
1748 }
1749 if (a[great] < pivot1) { // a[great] <= pivot2
1750 a[k] = a[less];
1751 a[less] = a[great];
1752 ++less;
1753 } else { // pivot1 <= a[great] <= pivot2
1754 a[k] = a[great];
1755 }
1756 /*
1757 * Here and below we use "a[i] = b; i--;" instead
1758 * of "a[i--] = b;" due to performance issue.
1759 */
1760 a[great] = ak;
1761 --great;
1762 }
1763 }
1764
1765 // Swap pivots into their final positions
1766 a[left] = a[less - 1]; a[less - 1] = pivot1;
1767 a[right] = a[great + 1]; a[great + 1] = pivot2;
1768
1769 // Sort left and right parts recursively, excluding known pivots
1770 sort(a, left, less - 2, leftmost);
1771 sort(a, great + 2, right, false);
1772
1773 /*
1774 * If center part is too large (comprises > 4/7 of the array),
1775 * swap internal pivot values to ends.
1776 */
1777 if (less < e1 && e5 < great) {
1778 /*
1779 * Skip elements, which are equal to pivot values.
1780 */
1781 while (a[less] == pivot1) {
1782 ++less;
1783 }
1784
1785 while (a[great] == pivot2) {
1786 --great;
1787 }
1788
1789 /*
1790 * Partitioning:
1791 *
1792 * left part center part right part
1793 * +----------------------------------------------------------+
1794 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1795 * +----------------------------------------------------------+
1796 * ^ ^ ^
1797 * | | |
1798 * less k great
1799 *
1800 * Invariants:
1801 *
1802 * all in (*, less) == pivot1
1803 * pivot1 < all in [less, k) < pivot2
1804 * all in (great, *) == pivot2
1805 *
1806 * Pointer k is the first index of ?-part.
1807 */
1808 outer:
1809 for (int k = less - 1; ++k <= great; ) {
1810 char ak = a[k];
1811 if (ak == pivot1) { // Move a[k] to left part
1812 a[k] = a[less];
1813 a[less] = ak;
1814 ++less;
1815 } else if (ak == pivot2) { // Move a[k] to right part
1816 while (a[great] == pivot2) {
1817 if (great-- == k) {
1818 break outer;
1819 }
1820 }
1821 if (a[great] == pivot1) { // a[great] < pivot2
1822 a[k] = a[less];
1823 /*
1824 * Even though a[great] equals to pivot1, the
1825 * assignment a[less] = pivot1 may be incorrect,
1826 * if a[great] and pivot1 are floating-point zeros
1827 * of different signs. Therefore in float and
1828 * double sorting methods we have to use more
1829 * accurate assignment a[less] = a[great].
1830 */
1831 a[less] = pivot1;
1832 ++less;
1833 } else { // pivot1 < a[great] < pivot2
1834 a[k] = a[great];
1835 }
1836 a[great] = ak;
1837 --great;
1838 }
1839 }
1840 }
1841
1842 // Sort center part recursively
1843 sort(a, less, great, false);
1844
1845 } else { // Partitioning with one pivot
1846 /*
1847 * Use the third of the five sorted elements as pivot.
1848 * This value is inexpensive approximation of the median.
1849 */
1850 char pivot = a[e3];
1851
1852 /*
1853 * Partitioning degenerates to the traditional 3-way
1854 * (or "Dutch National Flag") schema:
1855 *
1856 * left part center part right part
1857 * +-------------------------------------------------+
1858 * | < pivot | == pivot | ? | > pivot |
1859 * +-------------------------------------------------+
1860 * ^ ^ ^
1861 * | | |
1862 * less k great
1863 *
1864 * Invariants:
1865 *
1866 * all in (left, less) < pivot
1867 * all in [less, k) == pivot
1868 * all in (great, right) > pivot
1869 *
1870 * Pointer k is the first index of ?-part.
1871 */
1872 for (int k = less; k <= great; ++k) {
1873 if (a[k] == pivot) {
1874 continue;
1875 }
1876 char ak = a[k];
1877 if (ak < pivot) { // Move a[k] to left part
1878 a[k] = a[less];
1879 a[less] = ak;
1880 ++less;
1881 } else { // a[k] > pivot - Move a[k] to right part
1882 while (a[great] > pivot) {
1883 --great;
1884 }
1885 if (a[great] < pivot) { // a[great] <= pivot
1886 a[k] = a[less];
1887 a[less] = a[great];
1888 ++less;
1889 } else { // a[great] == pivot
1890 /*
1891 * Even though a[great] equals to pivot, the
1892 * assignment a[k] = pivot may be incorrect,
1893 * if a[great] and pivot are floating-point
1894 * zeros of different signs. Therefore in float
1895 * and double sorting methods we have to use
1896 * more accurate assignment a[k] = a[great].
1897 */
1898 a[k] = pivot;
1899 }
1900 a[great] = ak;
1901 --great;
1902 }
1903 }
1904
1905 /*
1906 * Sort left and right parts recursively.
1907 * All elements from center part are equal
1908 * and, therefore, already sorted.
1909 */
1910 sort(a, left, less - 1, leftmost);
1911 sort(a, great + 1, right, false);
1912 }
1913 }
1914
1915 /** The number of distinct byte values. */
1916 private static final int NUM_BYTE_VALUES = 1 << 8;
1917
1918 /**
1919 * Sorts the specified array.
1920 *
1921 * @param a the array to be sorted
1922 */
1923 public static void sort(byte[] a) {
1924 sort(a, 0, a.length - 1);
1925 }
1926
1927 /**
1928 * Sorts the specified range of the array.
1929 *
1930 * @param a the array to be sorted
1931 * @param left the index of the first element, inclusive, to be sorted
1932 * @param right the index of the last element, inclusive, to be sorted
1933 */
1934 public static void sort(byte[] a, int left, int right) {
1935 // Use counting sort on large arrays
1936 if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
1937 int[] count = new int[NUM_BYTE_VALUES];
1938
1939 for (int i = left - 1; ++i <= right;
1940 count[a[i] - Byte.MIN_VALUE]++
1941 );
1942 for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
1943 while (count[--i] == 0);
1944 byte value = (byte) (i + Byte.MIN_VALUE);
1945 int s = count[i];
1946
1947 do {
1948 a[--k] = value;
1949 } while (--s > 0);
1950 }
1951 } else { // Use insertion sort on small arrays
1952 for (int i = left, j = i; i < right; j = ++i) {
1953 byte ai = a[i + 1];
1954 while (ai < a[j]) {
1955 a[j + 1] = a[j];
1956 if (j-- == left) {
1957 break;
1958 }
1959 }
1960 a[j + 1] = ai;
1961 }
1962 }
1963 }
1964
1965 /**
1966 * Sorts the specified array.
1967 *
1968 * @param a the array to be sorted
1969 */
1970 public static void sort(float[] a) {
1971 sort(a, 0, a.length - 1);
1972 }
1973
1974 /**
1975 * Sorts the specified range of the array.
1976 *
1977 * @param a the array to be sorted
1978 * @param left the index of the first element, inclusive, to be sorted
1979 * @param right the index of the last element, inclusive, to be sorted
1980 */
1981 public static void sort(float[] a, int left, int right) {
1982 /*
1983 * Phase 1: Move NaNs to the end of the array.
1984 */
1985 while (left <= right && Float.isNaN(a[right])) {
1986 --right;
1987 }
1988 for (int k = right; --k >= left; ) {
1989 float ak = a[k];
1990 if (ak != ak) { // a[k] is NaN
1991 a[k] = a[right];
1992 a[right] = ak;
1993 --right;
1994 }
1995 }
1996
1997 /*
1998 * Phase 2: Sort everything except NaNs (which are already in place).
1999 */
2000 doSort(a, left, right);
2001
2002 /*
2003 * Phase 3: Place negative zeros before positive zeros.
2004 */
2005 int hi = right;
2006
2007 /*
2008 * Find the first zero, or first positive, or last negative element.
2009 */
2010 while (left < hi) {
2011 int middle = (left + hi) >>> 1;
2012 float middleValue = a[middle];
2013
2014 if (middleValue < 0.0f) {
2015 left = middle + 1;
2016 } else {
2017 hi = middle;
2018 }
2019 }
2020
2021 /*
2022 * Skip the last negative value (if any) or all leading negative zeros.
2023 */
2024 while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
2025 ++left;
2026 }
2027
2028 /*
2029 * Move negative zeros to the beginning of the sub-range.
2030 *
2031 * Partitioning:
2032 *
2033 * +----------------------------------------------------+
2034 * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
2035 * +----------------------------------------------------+
2036 * ^ ^ ^
2037 * | | |
2038 * left p k
2039 *
2040 * Invariants:
2041 *
2042 * all in (*, left) < 0.0
2043 * all in [left, p) == -0.0
2044 * all in [p, k) == 0.0
2045 * all in [k, right] >= 0.0
2046 *
2047 * Pointer k is the first index of ?-part.
2048 */
2049 for (int k = left, p = left - 1; ++k <= right; ) {
2050 float ak = a[k];
2051 if (ak != 0.0f) {
2052 break;
2053 }
2054 if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
2055 a[k] = 0.0f;
2056 a[++p] = -0.0f;
2057 }
2058 }
2059 }
2060
2061 /**
2062 * Sorts the specified range of the array.
2063 *
2064 * @param a the array to be sorted
2065 * @param left the index of the first element, inclusive, to be sorted
2066 * @param right the index of the last element, inclusive, to be sorted
2067 */
2068 private static void doSort(float[] a, int left, int right) {
2069 // Use Quicksort on small arrays
2070 if (right - left < QUICKSORT_THRESHOLD) {
2071 sort(a, left, right, true);
2072 return;
2073 }
2074
2075 /*
2076 * Index run[i] is the start of i-th run
2077 * (ascending or descending sequence).
2078 */
2079 int[] run = new int[MAX_RUN_COUNT + 1];
2080 int count = 0; run[0] = left;
2081
2082 // Check if the array is nearly sorted
2083 for (int k = left; k < right; run[count] = k) {
2084 if (a[k] < a[k + 1]) { // ascending
2085 while (++k <= right && a[k - 1] <= a[k]);
2086 } else if (a[k] > a[k + 1]) { // descending
2087 while (++k <= right && a[k - 1] >= a[k]);
2088 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
2089 float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
2090 }
2091 } else { // equal
2092 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
2093 if (--m == 0) {
2094 sort(a, left, right, true);
2095 return;
2096 }
2097 }
2098 }
2099
2100 /*
2101 * The array is not highly structured,
2102 * use Quicksort instead of merge sort.
2103 */
2104 if (++count == MAX_RUN_COUNT) {
2105 sort(a, left, right, true);
2106 return;
2107 }
2108 }
2109
2110 // Check special cases
2111 if (run[count] == right++) { // The last run contains one element
2112 run[++count] = right;
2113 } else if (count == 1) { // The array is already sorted
2114 return;
2115 }
2116
2117 /*
2118 * Create temporary array, which is used for merging.
2119 * Implementation note: variable "right" is increased by 1.
2120 */
2121 float[] b; byte odd = 0;
2122 for (int n = 1; (n <<= 1) < count; odd ^= 1);
2123
2124 if (odd == 0) {
2125 b = a; a = new float[b.length];
2126 for (int i = left - 1; ++i < right; a[i] = b[i]);
2127 } else {
2128 b = new float[a.length];
2129 }
2130
2131 // Merging
2132 for (int last; count > 1; count = last) {
2133 for (int k = (last = 0) + 2; k <= count; k += 2) {
2134 int hi = run[k], mi = run[k - 1];
2135 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
2136 if (q >= hi || p < mi && a[p] <= a[q]) {
2137 b[i] = a[p++];
2138 } else {
2139 b[i] = a[q++];
2140 }
2141 }
2142 run[++last] = hi;
2143 }
2144 if ((count & 1) != 0) {
2145 for (int i = right, lo = run[count - 1]; --i >= lo;
2146 b[i] = a[i]
2147 );
2148 run[++last] = right;
2149 }
2150 float[] t = a; a = b; b = t;
2151 }
2152 }
2153
2154 /**
2155 * Sorts the specified range of the array by Dual-Pivot Quicksort.
2156 *
2157 * @param a the array to be sorted
2158 * @param left the index of the first element, inclusive, to be sorted
2159 * @param right the index of the last element, inclusive, to be sorted
2160 * @param leftmost indicates if this part is the leftmost in the range
2161 */
2162 private static void sort(float[] a, int left, int right, boolean leftmost) {
2163 int length = right - left + 1;
2164
2165 // Use insertion sort on tiny arrays
2166 if (length < INSERTION_SORT_THRESHOLD) {
2167 if (leftmost) {
2168 /*
2169 * Traditional (without sentinel) insertion sort,
2170 * optimized for server VM, is used in case of
2171 * the leftmost part.
2172 */
2173 for (int i = left, j = i; i < right; j = ++i) {
2174 float ai = a[i + 1];
2175 while (ai < a[j]) {
2176 a[j + 1] = a[j];
2177 if (j-- == left) {
2178 break;
2179 }
2180 }
2181 a[j + 1] = ai;
2182 }
2183 } else {
2184 /*
2185 * Skip the longest ascending sequence.
2186 */
2187 do {
2188 if (left >= right) {
2189 return;
2190 }
2191 } while (a[++left] >= a[left - 1]);
2192
2193 /*
2194 * Every element from adjoining part plays the role
2195 * of sentinel, therefore this allows us to avoid the
2196 * left range check on each iteration. Moreover, we use
2197 * the more optimized algorithm, so called pair insertion
2198 * sort, which is faster (in the context of Quicksort)
2199 * than traditional implementation of insertion sort.
2200 */
2201 for (int k = left; ++left <= right; k = ++left) {
2202 float a1 = a[k], a2 = a[left];
2203
2204 if (a1 < a2) {
2205 a2 = a1; a1 = a[left];
2206 }
2207 while (a1 < a[--k]) {
2208 a[k + 2] = a[k];
2209 }
2210 a[++k + 1] = a1;
2211
2212 while (a2 < a[--k]) {
2213 a[k + 1] = a[k];
2214 }
2215 a[k + 1] = a2;
2216 }
2217 float last = a[right];
2218
2219 while (last < a[--right]) {
2220 a[right + 1] = a[right];
2221 }
2222 a[right + 1] = last;
2223 }
2224 return;
2225 }
2226
2227 // Inexpensive approximation of length / 7
2228 int seventh = (length >> 3) + (length >> 6) + 1;
2229
2230 /*
2231 * Sort five evenly spaced elements around (and including) the
2232 * center element in the range. These elements will be used for
2233 * pivot selection as described below. The choice for spacing
2234 * these elements was empirically determined to work well on
2235 * a wide variety of inputs.
2236 */
2237 int e3 = (left + right) >>> 1; // The midpoint
2238 int e2 = e3 - seventh;
2239 int e1 = e2 - seventh;
2240 int e4 = e3 + seventh;
2241 int e5 = e4 + seventh;
2242
2243 // Sort these elements using insertion sort
2244 if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
2245
2246 if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
2247 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2248 }
2249 if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
2250 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
2251 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2252 }
2253 }
2254 if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
2255 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
2256 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
2257 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2258 }
2259 }
2260 }
2261
2262 // Pointers
2263 int less = left; // The index of the first element of center part
2264 int great = right; // The index before the first element of right part
2265
2266 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
2267 /*
2268 * Use the second and fourth of the five sorted elements as pivots.
2269 * These values are inexpensive approximations of the first and
2270 * second terciles of the array. Note that pivot1 <= pivot2.
2271 */
2272 float pivot1 = a[e2];
2273 float pivot2 = a[e4];
2274
2275 /*
2276 * The first and the last elements to be sorted are moved to the
2277 * locations formerly occupied by the pivots. When partitioning
2278 * is complete, the pivots are swapped back into their final
2279 * positions, and excluded from subsequent sorting.
2280 */
2281 a[e2] = a[left];
2282 a[e4] = a[right];
2283
2284 /*
2285 * Skip elements, which are less or greater than pivot values.
2286 */
2287 while (a[++less] < pivot1);
2288 while (a[--great] > pivot2);
2289
2290 /*
2291 * Partitioning:
2292 *
2293 * left part center part right part
2294 * +--------------------------------------------------------------+
2295 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
2296 * +--------------------------------------------------------------+
2297 * ^ ^ ^
2298 * | | |
2299 * less k great
2300 *
2301 * Invariants:
2302 *
2303 * all in (left, less) < pivot1
2304 * pivot1 <= all in [less, k) <= pivot2
2305 * all in (great, right) > pivot2
2306 *
2307 * Pointer k is the first index of ?-part.
2308 */
2309 outer:
2310 for (int k = less - 1; ++k <= great; ) {
2311 float ak = a[k];
2312 if (ak < pivot1) { // Move a[k] to left part
2313 a[k] = a[less];
2314 /*
2315 * Here and below we use "a[i] = b; i++;" instead
2316 * of "a[i++] = b;" due to performance issue.
2317 */
2318 a[less] = ak;
2319 ++less;
2320 } else if (ak > pivot2) { // Move a[k] to right part
2321 while (a[great] > pivot2) {
2322 if (great-- == k) {
2323 break outer;
2324 }
2325 }
2326 if (a[great] < pivot1) { // a[great] <= pivot2
2327 a[k] = a[less];
2328 a[less] = a[great];
2329 ++less;
2330 } else { // pivot1 <= a[great] <= pivot2
2331 a[k] = a[great];
2332 }
2333 /*
2334 * Here and below we use "a[i] = b; i--;" instead
2335 * of "a[i--] = b;" due to performance issue.
2336 */
2337 a[great] = ak;
2338 --great;
2339 }
2340 }
2341
2342 // Swap pivots into their final positions
2343 a[left] = a[less - 1]; a[less - 1] = pivot1;
2344 a[right] = a[great + 1]; a[great + 1] = pivot2;
2345
2346 // Sort left and right parts recursively, excluding known pivots
2347 sort(a, left, less - 2, leftmost);
2348 sort(a, great + 2, right, false);
2349
2350 /*
2351 * If center part is too large (comprises > 4/7 of the array),
2352 * swap internal pivot values to ends.
2353 */
2354 if (less < e1 && e5 < great) {
2355 /*
2356 * Skip elements, which are equal to pivot values.
2357 */
2358 while (a[less] == pivot1) {
2359 ++less;
2360 }
2361
2362 while (a[great] == pivot2) {
2363 --great;
2364 }
2365
2366 /*
2367 * Partitioning:
2368 *
2369 * left part center part right part
2370 * +----------------------------------------------------------+
2371 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
2372 * +----------------------------------------------------------+
2373 * ^ ^ ^
2374 * | | |
2375 * less k great
2376 *
2377 * Invariants:
2378 *
2379 * all in (*, less) == pivot1
2380 * pivot1 < all in [less, k) < pivot2
2381 * all in (great, *) == pivot2
2382 *
2383 * Pointer k is the first index of ?-part.
2384 */
2385 outer:
2386 for (int k = less - 1; ++k <= great; ) {
2387 float ak = a[k];
2388 if (ak == pivot1) { // Move a[k] to left part
2389 a[k] = a[less];
2390 a[less] = ak;
2391 ++less;
2392 } else if (ak == pivot2) { // Move a[k] to right part
2393 while (a[great] == pivot2) {
2394 if (great-- == k) {
2395 break outer;
2396 }
2397 }
2398 if (a[great] == pivot1) { // a[great] < pivot2
2399 a[k] = a[less];
2400 /*
2401 * Even though a[great] equals to pivot1, the
2402 * assignment a[less] = pivot1 may be incorrect,
2403 * if a[great] and pivot1 are floating-point zeros
2404 * of different signs. Therefore in float and
2405 * double sorting methods we have to use more
2406 * accurate assignment a[less] = a[great].
2407 */
2408 a[less] = a[great];
2409 ++less;
2410 } else { // pivot1 < a[great] < pivot2
2411 a[k] = a[great];
2412 }
2413 a[great] = ak;
2414 --great;
2415 }
2416 }
2417 }
2418
2419 // Sort center part recursively
2420 sort(a, less, great, false);
2421
2422 } else { // Partitioning with one pivot
2423 /*
2424 * Use the third of the five sorted elements as pivot.
2425 * This value is inexpensive approximation of the median.
2426 */
2427 float pivot = a[e3];
2428
2429 /*
2430 * Partitioning degenerates to the traditional 3-way
2431 * (or "Dutch National Flag") schema:
2432 *
2433 * left part center part right part
2434 * +-------------------------------------------------+
2435 * | < pivot | == pivot | ? | > pivot |
2436 * +-------------------------------------------------+
2437 * ^ ^ ^
2438 * | | |
2439 * less k great
2440 *
2441 * Invariants:
2442 *
2443 * all in (left, less) < pivot
2444 * all in [less, k) == pivot
2445 * all in (great, right) > pivot
2446 *
2447 * Pointer k is the first index of ?-part.
2448 */
2449 for (int k = less; k <= great; ++k) {
2450 if (a[k] == pivot) {
2451 continue;
2452 }
2453 float ak = a[k];
2454 if (ak < pivot) { // Move a[k] to left part
2455 a[k] = a[less];
2456 a[less] = ak;
2457 ++less;
2458 } else { // a[k] > pivot - Move a[k] to right part
2459 while (a[great] > pivot) {
2460 --great;
2461 }
2462 if (a[great] < pivot) { // a[great] <= pivot
2463 a[k] = a[less];
2464 a[less] = a[great];
2465 ++less;
2466 } else { // a[great] == pivot
2467 /*
2468 * Even though a[great] equals to pivot, the
2469 * assignment a[k] = pivot may be incorrect,
2470 * if a[great] and pivot are floating-point
2471 * zeros of different signs. Therefore in float
2472 * and double sorting methods we have to use
2473 * more accurate assignment a[k] = a[great].
2474 */
2475 a[k] = a[great];
2476 }
2477 a[great] = ak;
2478 --great;
2479 }
2480 }
2481
2482 /*
2483 * Sort left and right parts recursively.
2484 * All elements from center part are equal
2485 * and, therefore, already sorted.
2486 */
2487 sort(a, left, less - 1, leftmost);
2488 sort(a, great + 1, right, false);
2489 }
2490 }
2491
2492 /**
2493 * Sorts the specified array.
2494 *
2495 * @param a the array to be sorted
2496 */
2497 public static void sort(double[] a) {
2498 sort(a, 0, a.length - 1);
2499 }
2500
2501 /**
2502 * Sorts the specified range of the array.
2503 *
2504 * @param a the array to be sorted
2505 * @param left the index of the first element, inclusive, to be sorted
2506 * @param right the index of the last element, inclusive, to be sorted
2507 */
2508 public static void sort(double[] a, int left, int right) {
2509 /*
2510 * Phase 1: Move NaNs to the end of the array.
2511 */
2512 while (left <= right && Double.isNaN(a[right])) {
2513 --right;
2514 }
2515 for (int k = right; --k >= left; ) {
2516 double ak = a[k];
2517 if (ak != ak) { // a[k] is NaN
2518 a[k] = a[right];
2519 a[right] = ak;
2520 --right;
2521 }
2522 }
2523
2524 /*
2525 * Phase 2: Sort everything except NaNs (which are already in place).
2526 */
2527 doSort(a, left, right);
2528
2529 /*
2530 * Phase 3: Place negative zeros before positive zeros.
2531 */
2532 int hi = right;
2533
2534 /*
2535 * Find the first zero, or first positive, or last negative element.
2536 */
2537 while (left < hi) {
2538 int middle = (left + hi) >>> 1;
2539 double middleValue = a[middle];
2540
2541 if (middleValue < 0.0d) {
2542 left = middle + 1;
2543 } else {
2544 hi = middle;
2545 }
2546 }
2547
2548 /*
2549 * Skip the last negative value (if any) or all leading negative zeros.
2550 */
2551 while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
2552 ++left;
2553 }
2554
2555 /*
2556 * Move negative zeros to the beginning of the sub-range.
2557 *
2558 * Partitioning:
2559 *
2560 * +----------------------------------------------------+
2561 * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
2562 * +----------------------------------------------------+
2563 * ^ ^ ^
2564 * | | |
2565 * left p k
2566 *
2567 * Invariants:
2568 *
2569 * all in (*, left) < 0.0
2570 * all in [left, p) == -0.0
2571 * all in [p, k) == 0.0
2572 * all in [k, right] >= 0.0
2573 *
2574 * Pointer k is the first index of ?-part.
2575 */
2576 for (int k = left, p = left - 1; ++k <= right; ) {
2577 double ak = a[k];
2578 if (ak != 0.0d) {
2579 break;
2580 }
2581 if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
2582 a[k] = 0.0d;
2583 a[++p] = -0.0d;
2584 }
2585 }
2586 }
2587
2588 /**
2589 * Sorts the specified range of the array.
2590 *
2591 * @param a the array to be sorted
2592 * @param left the index of the first element, inclusive, to be sorted
2593 * @param right the index of the last element, inclusive, to be sorted
2594 */
2595 private static void doSort(double[] a, int left, int right) {
2596 // Use Quicksort on small arrays
2597 if (right - left < QUICKSORT_THRESHOLD) {
2598 sort(a, left, right, true);
2599 return;
2600 }
2601
2602 /*
2603 * Index run[i] is the start of i-th run
2604 * (ascending or descending sequence).
2605 */
2606 int[] run = new int[MAX_RUN_COUNT + 1];
2607 int count = 0; run[0] = left;
2608
2609 // Check if the array is nearly sorted
2610 for (int k = left; k < right; run[count] = k) {
2611 if (a[k] < a[k + 1]) { // ascending
2612 while (++k <= right && a[k - 1] <= a[k]);
2613 } else if (a[k] > a[k + 1]) { // descending
2614 while (++k <= right && a[k - 1] >= a[k]);
2615 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
2616 double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
2617 }
2618 } else { // equal
2619 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
2620 if (--m == 0) {
2621 sort(a, left, right, true);
2622 return;
2623 }
2624 }
2625 }
2626
2627 /*
2628 * The array is not highly structured,
2629 * use Quicksort instead of merge sort.
2630 */
2631 if (++count == MAX_RUN_COUNT) {
2632 sort(a, left, right, true);
2633 return;
2634 }
2635 }
2636
2637 // Check special cases
2638 if (run[count] == right++) { // The last run contains one element
2639 run[++count] = right;
2640 } else if (count == 1) { // The array is already sorted
2641 return;
2642 }
2643
2644 /*
2645 * Create temporary array, which is used for merging.
2646 * Implementation note: variable "right" is increased by 1.
2647 */
2648 double[] b; byte odd = 0;
2649 for (int n = 1; (n <<= 1) < count; odd ^= 1);
2650
2651 if (odd == 0) {
2652 b = a; a = new double[b.length];
2653 for (int i = left - 1; ++i < right; a[i] = b[i]);
2654 } else {
2655 b = new double[a.length];
2656 }
2657
2658 // Merging
2659 for (int last; count > 1; count = last) {
2660 for (int k = (last = 0) + 2; k <= count; k += 2) {
2661 int hi = run[k], mi = run[k - 1];
2662 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
2663 if (q >= hi || p < mi && a[p] <= a[q]) {
2664 b[i] = a[p++];
2665 } else {
2666 b[i] = a[q++];
2667 }
2668 }
2669 run[++last] = hi;
2670 }
2671 if ((count & 1) != 0) {
2672 for (int i = right, lo = run[count - 1]; --i >= lo;
2673 b[i] = a[i]
2674 );
2675 run[++last] = right;
2676 }
2677 double[] t = a; a = b; b = t;
2678 }
2679 }
2680
2681 /**
2682 * Sorts the specified range of the array by Dual-Pivot Quicksort.
2683 *
2684 * @param a the array to be sorted
2685 * @param left the index of the first element, inclusive, to be sorted
2686 * @param right the index of the last element, inclusive, to be sorted
2687 * @param leftmost indicates if this part is the leftmost in the range
2688 */
2689 private static void sort(double[] a, int left, int right, boolean leftmost) {
2690 int length = right - left + 1;
2691
2692 // Use insertion sort on tiny arrays
2693 if (length < INSERTION_SORT_THRESHOLD) {
2694 if (leftmost) {
2695 /*
2696 * Traditional (without sentinel) insertion sort,
2697 * optimized for server VM, is used in case of
2698 * the leftmost part.
2699 */
2700 for (int i = left, j = i; i < right; j = ++i) {
2701 double ai = a[i + 1];
2702 while (ai < a[j]) {
2703 a[j + 1] = a[j];
2704 if (j-- == left) {
2705 break;
2706 }
2707 }
2708 a[j + 1] = ai;
2709 }
2710 } else {
2711 /*
2712 * Skip the longest ascending sequence.
2713 */
2714 do {
2715 if (left >= right) {
2716 return;
2717 }
2718 } while (a[++left] >= a[left - 1]);
2719
2720 /*
2721 * Every element from adjoining part plays the role
2722 * of sentinel, therefore this allows us to avoid the
2723 * left range check on each iteration. Moreover, we use
2724 * the more optimized algorithm, so called pair insertion
2725 * sort, which is faster (in the context of Quicksort)
2726 * than traditional implementation of insertion sort.
2727 */
2728 for (int k = left; ++left <= right; k = ++left) {
2729 double a1 = a[k], a2 = a[left];
2730
2731 if (a1 < a2) {
2732 a2 = a1; a1 = a[left];
2733 }
2734 while (a1 < a[--k]) {
2735 a[k + 2] = a[k];
2736 }
2737 a[++k + 1] = a1;
2738
2739 while (a2 < a[--k]) {
2740 a[k + 1] = a[k];
2741 }
2742 a[k + 1] = a2;
2743 }
2744 double last = a[right];
2745
2746 while (last < a[--right]) {
2747 a[right + 1] = a[right];
2748 }
2749 a[right + 1] = last;
2750 }
2751 return;
2752 }
2753
2754 // Inexpensive approximation of length / 7
2755 int seventh = (length >> 3) + (length >> 6) + 1;
2756
2757 /*
2758 * Sort five evenly spaced elements around (and including) the
2759 * center element in the range. These elements will be used for
2760 * pivot selection as described below. The choice for spacing
2761 * these elements was empirically determined to work well on
2762 * a wide variety of inputs.
2763 */
2764 int e3 = (left + right) >>> 1; // The midpoint
2765 int e2 = e3 - seventh;
2766 int e1 = e2 - seventh;
2767 int e4 = e3 + seventh;
2768 int e5 = e4 + seventh;
2769
2770 // Sort these elements using insertion sort
2771 if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
2772
2773 if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
2774 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2775 }
2776 if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
2777 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
2778 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2779 }
2780 }
2781 if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
2782 if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
2783 if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
2784 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
2785 }
2786 }
2787 }
2788
2789 // Pointers
2790 int less = left; // The index of the first element of center part
2791 int great = right; // The index before the first element of right part
2792
2793 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
2794 /*
2795 * Use the second and fourth of the five sorted elements as pivots.
2796 * These values are inexpensive approximations of the first and
2797 * second terciles of the array. Note that pivot1 <= pivot2.
2798 */
2799 double pivot1 = a[e2];
2800 double pivot2 = a[e4];
2801
2802 /*
2803 * The first and the last elements to be sorted are moved to the
2804 * locations formerly occupied by the pivots. When partitioning
2805 * is complete, the pivots are swapped back into their final
2806 * positions, and excluded from subsequent sorting.
2807 */
2808 a[e2] = a[left];
2809 a[e4] = a[right];
2810
2811 /*
2812 * Skip elements, which are less or greater than pivot values.
2813 */
2814 while (a[++less] < pivot1);
2815 while (a[--great] > pivot2);
2816
2817 /*
2818 * Partitioning:
2819 *
2820 * left part center part right part
2821 * +--------------------------------------------------------------+
2822 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
2823 * +--------------------------------------------------------------+
2824 * ^ ^ ^
2825 * | | |
2826 * less k great
2827 *
2828 * Invariants:
2829 *
2830 * all in (left, less) < pivot1
2831 * pivot1 <= all in [less, k) <= pivot2
2832 * all in (great, right) > pivot2
2833 *
2834 * Pointer k is the first index of ?-part.
2835 */
2836 outer:
2837 for (int k = less - 1; ++k <= great; ) {
2838 double ak = a[k];
2839 if (ak < pivot1) { // Move a[k] to left part
2840 a[k] = a[less];
2841 /*
2842 * Here and below we use "a[i] = b; i++;" instead
2843 * of "a[i++] = b;" due to performance issue.
2844 */
2845 a[less] = ak;
2846 ++less;
2847 } else if (ak > pivot2) { // Move a[k] to right part
2848 while (a[great] > pivot2) {
2849 if (great-- == k) {
2850 break outer;
2851 }
2852 }
2853 if (a[great] < pivot1) { // a[great] <= pivot2
2854 a[k] = a[less];
2855 a[less] = a[great];
2856 ++less;
2857 } else { // pivot1 <= a[great] <= pivot2
2858 a[k] = a[great];
2859 }
2860 /*
2861 * Here and below we use "a[i] = b; i--;" instead
2862 * of "a[i--] = b;" due to performance issue.
2863 */
2864 a[great] = ak;
2865 --great;
2866 }
2867 }
2868
2869 // Swap pivots into their final positions
2870 a[left] = a[less - 1]; a[less - 1] = pivot1;
2871 a[right] = a[great + 1]; a[great + 1] = pivot2;
2872
2873 // Sort left and right parts recursively, excluding known pivots
2874 sort(a, left, less - 2, leftmost);
2875 sort(a, great + 2, right, false);
2876
2877 /*
2878 * If center part is too large (comprises > 4/7 of the array),
2879 * swap internal pivot values to ends.
2880 */
2881 if (less < e1 && e5 < great) {
2882 /*
2883 * Skip elements, which are equal to pivot values.
2884 */
2885 while (a[less] == pivot1) {
2886 ++less;
2887 }
2888
2889 while (a[great] == pivot2) {
2890 --great;
2891 }
2892
2893 /*
2894 * Partitioning:
2895 *
2896 * left part center part right part
2897 * +----------------------------------------------------------+
2898 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
2899 * +----------------------------------------------------------+
2900 * ^ ^ ^
2901 * | | |
2902 * less k great
2903 *
2904 * Invariants:
2905 *
2906 * all in (*, less) == pivot1
2907 * pivot1 < all in [less, k) < pivot2
2908 * all in (great, *) == pivot2
2909 *
2910 * Pointer k is the first index of ?-part.
2911 */
2912 outer:
2913 for (int k = less - 1; ++k <= great; ) {
2914 double ak = a[k];
2915 if (ak == pivot1) { // Move a[k] to left part
2916 a[k] = a[less];
2917 a[less] = ak;
2918 ++less;
2919 } else if (ak == pivot2) { // Move a[k] to right part
2920 while (a[great] == pivot2) {
2921 if (great-- == k) {
2922 break outer;
2923 }
2924 }
2925 if (a[great] == pivot1) { // a[great] < pivot2
2926 a[k] = a[less];
2927 /*
2928 * Even though a[great] equals to pivot1, the
2929 * assignment a[less] = pivot1 may be incorrect,
2930 * if a[great] and pivot1 are floating-point zeros
2931 * of different signs. Therefore in float and
2932 * double sorting methods we have to use more
2933 * accurate assignment a[less] = a[great].
2934 */
2935 a[less] = a[great];
2936 ++less;
2937 } else { // pivot1 < a[great] < pivot2
2938 a[k] = a[great];
2939 }
2940 a[great] = ak;
2941 --great;
2942 }
2943 }
2944 }
2945
2946 // Sort center part recursively
2947 sort(a, less, great, false);
2948
2949 } else { // Partitioning with one pivot
2950 /*
2951 * Use the third of the five sorted elements as pivot.
2952 * This value is inexpensive approximation of the median.
2953 */
2954 double pivot = a[e3];
2955
2956 /*
2957 * Partitioning degenerates to the traditional 3-way
2958 * (or "Dutch National Flag") schema:
2959 *
2960 * left part center part right part
2961 * +-------------------------------------------------+
2962 * | < pivot | == pivot | ? | > pivot |
2963 * +-------------------------------------------------+
2964 * ^ ^ ^
2965 * | | |
2966 * less k great
2967 *
2968 * Invariants:
2969 *
2970 * all in (left, less) < pivot
2971 * all in [less, k) == pivot
2972 * all in (great, right) > pivot
2973 *
2974 * Pointer k is the first index of ?-part.
2975 */
2976 for (int k = less; k <= great; ++k) {
2977 if (a[k] == pivot) {
2978 continue;
2979 }
2980 double ak = a[k];
2981 if (ak < pivot) { // Move a[k] to left part
2982 a[k] = a[less];
2983 a[less] = ak;
2984 ++less;
2985 } else { // a[k] > pivot - Move a[k] to right part
2986 while (a[great] > pivot) {
2987 --great;
2988 }
2989 if (a[great] < pivot) { // a[great] <= pivot
2990 a[k] = a[less];
2991 a[less] = a[great];
2992 ++less;
2993 } else { // a[great] == pivot
2994 /*
2995 * Even though a[great] equals to pivot, the
2996 * assignment a[k] = pivot may be incorrect,
2997 * if a[great] and pivot are floating-point
2998 * zeros of different signs. Therefore in float
2999 * and double sorting methods we have to use
3000 * more accurate assignment a[k] = a[great].
3001 */
3002 a[k] = a[great];
3003 }
3004 a[great] = ak;
3005 --great;
3006 }
3007 }
3008
3009 /*
3010 * Sort left and right parts recursively.
3011 * All elements from center part are equal
3012 * and, therefore, already sorted.
3013 */
3014 sort(a, left, less - 1, leftmost);
3015 sort(a, great + 1, right, false);
3016 }
3017 }
3018 }