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