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