1 /*
2 * Copyright (c) 2018, 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 import java.util.concurrent.ForkJoinTask;
29 import java.util.concurrent.RecursiveTask;
30
31 /**
32 * This class implements sorting algorithms by Vladimir Yaroslavskiy,
33 such as Merging sort, the pair, nano and optimized insertion sorts,
34 * counting sort and heap sort, invoked from the Dual-Pivot Quicksort.
35 *
36 * @author Vladimir Yaroslavskiy
37 *
38 * @version 2018.02.18
39 * @since 10
40 */
41 final class SortingAlgorithms {
42
43 /**
44 * Prevents instantiation.
45 */
46 private SortingAlgorithms() {}
47
48 /**
49 * The minimal number of runs, required by parallel Merging sort.
50 */
51 private static final int MIN_PARALLEL_RUNS_COUNT = 4;
52
53 /**
54 * If the length of an array to be sorted is greater than this
55 * constant, Merging sort is used in preference to Quicksort.
56 */
57 private static final int MERGING_SORT_THRESHOLD = 2048;
58
59 /**
60 * Calculates the maximum number of runs.
61 *
62 * @param length the array length
63 * @return the maximum number of runs
64 */
65 private static int getMaxRunCount(int length) {
66 return length > 2048000 ? 2000 : length >> 10 | 5;
67 }
68
69 /**
70 * This class implements the parallel Merging sort.
71 */
72 @SuppressWarnings("serial")
73 private static class Merger<T> extends RecursiveTask<T> {
74
75 Merger(T a, T b, boolean src, int offset, int[] run, int lo, int hi) {
76 this.a = a;
77 this.b = b;
78 this.src = src;
79 this.offset = offset;
80 this.run = run;
81 this.lo = lo;
82 this.hi = hi;
83 }
84
85 @Override
86 @SuppressWarnings("unchecked")
87 protected T compute() {
88 Class<?> clazz = a.getClass();
89
90 if (clazz == int[].class) {
91 return (T) merge((int[]) a, (int[]) b, src, true, offset, run, lo, hi);
92 }
93 if (clazz == long[].class) {
94 return (T) merge((long[]) a, (long[]) b, src, true, offset, run, lo, hi);
95 }
96 if (clazz == char[].class) {
97 return (T) merge((char[]) a, (char[]) b, src, true, offset, run, lo, hi);
98 }
99 if (clazz == short[].class) {
100 return (T) merge((short[]) a, (short[]) b, src, true, offset, run, lo, hi);
101 }
102 if (clazz == float[].class) {
103 return (T) merge((float[]) a, (float[]) b, src, true, offset, run, lo, hi);
104 }
105 if (clazz == double[].class) {
106 return (T) merge((double[]) a, (double[]) b, src, true, offset, run, lo, hi);
107 }
108 throw new IllegalArgumentException(
109 "Unknown type of array: " + clazz.getName());
110 }
111
112 private T a;
113 private T b;
114 private boolean src;
115 private int offset;
116 private int[] run;
117 private int lo;
118 private int hi;
119 }
120
121 /**
122 * Tries to sort the specified range of the array by the Merging sort.
123 *
124 * @param a the array to be sorted
125 * @param parallel indicates whether merging is performed in parallel
126 * @param low the index of the first element, inclusive, to be sorted
127 * @param high the index of the last element, exclusive, to be sorted
128 * @return true if the given array is finally sorted, false otherwise
129 */
130 static boolean mergingSort(int[] a, boolean parallel, int low, int high) {
131 int length = high - low;
132
133 if (length < MERGING_SORT_THRESHOLD) {
134 return false;
135 }
136
137 /*
138 * Index run[i] is the start of i-th run.
139 * A run is a subsequence of elements
140 * in ascending or descending order.
141 */
142 int max = getMaxRunCount(length);
143 int[] run = new int[max + 1];
144 int count = 0, last = low; run[0] = low;
145
146 /*
147 * Check if the array is highly structured.
148 */
149 for (int k = low + 1; k < high && count < max; ) {
150 if (a[k - 1] < a[k]) {
151
152 // Identify ascending sequence
153 while (++k < high && a[k - 1] <= a[k]);
154
155 } else if (a[k - 1] > a[k]) {
156
157 // Identify descending sequence
158 while (++k < high && a[k - 1] >= a[k]);
159
160 // Reverse the run into ascending order
161 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
162 int ai = a[i]; a[i] = a[j]; a[j] = ai;
163 }
164 } else { // Sequence with equal elements
165 for (int ak = a[k]; ++k < high && ak == a[k]; );
166
167 if (k < high) {
168 continue;
169 }
170 }
171
172 if (count == 0 || a[last - 1] > a[last]) {
173 ++count;
174 }
175 run[count] = (last = k);
176 }
177
178 if (count < max && count > 1) {
179 /*
180 * The array is highly structured, therefore merge all runs.
181 */
182 merge(a, new int[length], true, parallel, low, run, 0, count);
183 }
184 return count < max;
185 }
186
187 /**
188 * Merges the specified runs.
189 *
190 * @param a the source array
191 * @param b the temporary buffer
192 * @param src specifies the type of the target: source or buffer
193 * @param parallel indicates whether merging is performed in parallel
194 * @param offset the start index of the source, inclusive
195 * @param run the start indexes of the runs, inclusive
196 * @param lo the start index of the first run, inclusive
197 * @param hi the start index of the last run, inclusive
198 * @return the target where runs are merged
199 */
200 private static int[] merge(int[] a, int[] b, boolean src,
201 boolean parallel, int offset, int[] run, int lo, int hi) {
202
203 if (hi - lo == 1) {
204 if (src) {
205 return a;
206 }
207 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
208 b[--j] = a[--i]
209 );
210 return b;
211 }
212 int mi = (lo + hi) >>> 1;
213
214 int[] a1, a2; // the left and the right halves to be merged
215
216 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
217 Merger<int[]> merger1 = new Merger<int[]>(a, b, !src, offset, run, lo, mi);
218 Merger<int[]> merger2 = new Merger<int[]>(a, b, true, offset, run, mi, hi);
219
220 ForkJoinTask.invokeAll(merger1, merger2);
221
222 a1 = merger1.getRawResult();
223 a2 = merger2.getRawResult();
224 } else {
225 a1 = merge(a, b, !src, false, offset, run, lo, mi);
226 a2 = merge(a, b, true, false, offset, run, mi, hi);
227 }
228 return merge(
229 a1 == a ? b : a,
230 a1 == a ? run[lo] - offset : run[lo],
231 a1,
232 a1 == b ? run[lo] - offset : run[lo],
233 a1 == b ? run[mi] - offset : run[mi],
234 a2,
235 a2 == b ? run[mi] - offset : run[mi],
236 a2 == b ? run[hi] - offset : run[hi]);
237 }
238
239 /**
240 * Merges the sorted halves.
241 *
242 * @param dst the destination where halves are merged
243 * @param k the start index of the destination, inclusive
244 * @param a1 the first half
245 * @param i the start index of the first half, inclusive
246 * @param hi the end index of the first half, exclusive
247 * @param a2 the second half
248 * @param j the start index of the second half, inclusive
249 * @param hj the end index of the second half, exclusive
250 * @return the merged halves
251 */
252 private static int[] merge(int[] dst, int k,
253 int[] a1, int i, int hi, int[] a2, int j, int hj) {
254
255 while (true) {
256 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
257
258 if (i == hi) {
259 while (j < hj) {
260 dst[k++] = a2[j++];
261 }
262 return dst;
263 }
264 if (j == hj) {
265 while (i < hi) {
266 dst[k++] = a1[i++];
267 }
268 return dst;
269 }
270 }
271 }
272
273 /**
274 * Tries to sort the specified range of the array by the Merging sort.
275 *
276 * @param a the array to be sorted
277 * @param parallel indicates whether merging is performed in parallel
278 * @param low the index of the first element, inclusive, to be sorted
279 * @param high the index of the last element, exclusive, to be sorted
280 * @return true if the given array is finally sorted, false otherwise
281 */
282 static boolean mergingSort(long[] a, boolean parallel, int low, int high) {
283 int length = high - low;
284
285 if (length < MERGING_SORT_THRESHOLD) {
286 return false;
287 }
288
289 /*
290 * Index run[i] is the start of i-th run.
291 * A run is a subsequence of elements
292 * in ascending or descending order.
293 */
294 int max = getMaxRunCount(length);
295 int[] run = new int[max + 1];
296 int count = 0, last = low; run[0] = low;
297
298 /*
299 * Check if the array is highly structured.
300 */
301 for (int k = low + 1; k < high && count < max; ) {
302 if (a[k - 1] < a[k]) {
303
304 // Identify ascending sequence
305 while (++k < high && a[k - 1] <= a[k]);
306
307 } else if (a[k - 1] > a[k]) {
308
309 // Identify descending sequence
310 while (++k < high && a[k - 1] >= a[k]);
311
312 // Reverse the run into ascending order
313 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
314 long ai = a[i]; a[i] = a[j]; a[j] = ai;
315 }
316 } else { // Sequence with equal elements
317 for (long ak = a[k]; ++k < high && ak == a[k]; );
318
319 if (k < high) {
320 continue;
321 }
322 }
323
324 if (count == 0 || a[last - 1] > a[last]) {
325 ++count;
326 }
327 run[count] = (last = k);
328 }
329
330 if (count < max && count > 1) {
331 /*
332 * The array is highly structured, therefore merge all runs.
333 */
334 merge(a, new long[length], true, parallel, low, run, 0, count);
335 }
336 return count < max;
337 }
338
339 /**
340 * Merges the specified runs.
341 *
342 * @param a the source array
343 * @param b the temporary buffer
344 * @param src specifies the type of the target: source or buffer
345 * @param parallel indicates whether merging is performed in parallel
346 * @param offset the start index of the source, inclusive
347 * @param run the start indexes of the runs, inclusive
348 * @param lo the start index of the first run, inclusive
349 * @param hi the start index of the last run, inclusive
350 * @return the target where runs are merged
351 */
352 private static long[] merge(long[] a, long[] b, boolean src,
353 boolean parallel, int offset, int[] run, int lo, int hi) {
354
355 if (hi - lo == 1) {
356 if (src) {
357 return a;
358 }
359 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
360 b[--j] = a[--i]
361 );
362 return b;
363 }
364 int mi = (lo + hi) >>> 1;
365
366 long[] a1, a2; // the left and the right halves to be merged
367
368 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
369 Merger<long[]> merger1 = new Merger<long[]>(a, b, !src, offset, run, lo, mi);
370 Merger<long[]> merger2 = new Merger<long[]>(a, b, true, offset, run, mi, hi);
371
372 ForkJoinTask.invokeAll(merger1, merger2);
373
374 a1 = merger1.getRawResult();
375 a2 = merger2.getRawResult();
376 } else {
377 a1 = merge(a, b, !src, false, offset, run, lo, mi);
378 a2 = merge(a, b, true, false, offset, run, mi, hi);
379 }
380 return merge(
381 a1 == a ? b : a,
382 a1 == a ? run[lo] - offset : run[lo],
383 a1,
384 a1 == b ? run[lo] - offset : run[lo],
385 a1 == b ? run[mi] - offset : run[mi],
386 a2,
387 a2 == b ? run[mi] - offset : run[mi],
388 a2 == b ? run[hi] - offset : run[hi]);
389 }
390
391 /**
392 * Merges the sorted halves.
393 *
394 * @param dst the destination where halves are merged
395 * @param k the start index of the destination, inclusive
396 * @param a1 the first half
397 * @param i the start index of the first half, inclusive
398 * @param hi the end index of the first half, exclusive
399 * @param a2 the second half
400 * @param j the start index of the second half, inclusive
401 * @param hj the end index of the second half, exclusive
402 * @return the merged halves
403 */
404 private static long[] merge(long[] dst, int k,
405 long[] a1, int i, int hi, long[] a2, int j, int hj) {
406
407 while (true) {
408 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
409
410 if (i == hi) {
411 while (j < hj) {
412 dst[k++] = a2[j++];
413 }
414 return dst;
415 }
416 if (j == hj) {
417 while (i < hi) {
418 dst[k++] = a1[i++];
419 }
420 return dst;
421 }
422 }
423 }
424
425 /**
426 * Tries to sort the specified range of the array by the Merging sort.
427 *
428 * @param a the array to be sorted
429 * @param parallel indicates whether merging is performed in parallel
430 * @param low the index of the first element, inclusive, to be sorted
431 * @param high the index of the last element, exclusive, to be sorted
432 * @return true if the given array is finally sorted, false otherwise
433 */
434 static boolean mergingSort(char[] a, boolean parallel, int low, int high) {
435 int length = high - low;
436
437 if (length < MERGING_SORT_THRESHOLD) {
438 return false;
439 }
440
441 /*
442 * Index run[i] is the start of i-th run.
443 * A run is a subsequence of elements
444 * in ascending or descending order.
445 */
446 int max = getMaxRunCount(length);
447 int[] run = new int[max + 1];
448 int count = 0, last = low; run[0] = low;
449
450 /*
451 * Check if the array is highly structured.
452 */
453 for (int k = low + 1; k < high && count < max; ) {
454 if (a[k - 1] < a[k]) {
455
456 // Identify ascending sequence
457 while (++k < high && a[k - 1] <= a[k]);
458
459 } else if (a[k - 1] > a[k]) {
460
461 // Identify descending sequence
462 while (++k < high && a[k - 1] >= a[k]);
463
464 // Reverse the run into ascending order
465 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
466 char ai = a[i]; a[i] = a[j]; a[j] = ai;
467 }
468 } else { // Sequence with equal elements
469 for (char ak = a[k]; ++k < high && ak == a[k]; );
470
471 if (k < high) {
472 continue;
473 }
474 }
475
476 if (count == 0 || a[last - 1] > a[last]) {
477 ++count;
478 }
479 run[count] = (last = k);
480 }
481
482 if (count < max && count > 1) {
483 /*
484 * The array is highly structured, therefore merge all runs.
485 */
486 merge(a, new char[length], true, parallel, low, run, 0, count);
487 }
488 return count < max;
489 }
490
491 /**
492 * Merges the specified runs.
493 *
494 * @param a the source array
495 * @param b the temporary buffer
496 * @param src specifies the type of the target: source or buffer
497 * @param parallel indicates whether merging is performed in parallel
498 * @param offset the start index of the source, inclusive
499 * @param run the start indexes of the runs, inclusive
500 * @param lo the start index of the first run, inclusive
501 * @param hi the start index of the last run, inclusive
502 * @return the target where runs are merged
503 */
504 private static char[] merge(char[] a, char[] b, boolean src,
505 boolean parallel, int offset, int[] run, int lo, int hi) {
506
507 if (hi - lo == 1) {
508 if (src) {
509 return a;
510 }
511 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
512 b[--j] = a[--i]
513 );
514 return b;
515 }
516 int mi = (lo + hi) >>> 1;
517
518 char[] a1, a2; // the left and the right halves to be merged
519
520 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
521 Merger<char[]> merger1 = new Merger<char[]>(a, b, !src, offset, run, lo, mi);
522 Merger<char[]> merger2 = new Merger<char[]>(a, b, true, offset, run, mi, hi);
523
524 ForkJoinTask.invokeAll(merger1, merger2);
525
526 a1 = merger1.getRawResult();
527 a2 = merger2.getRawResult();
528 } else {
529 a1 = merge(a, b, !src, false, offset, run, lo, mi);
530 a2 = merge(a, b, true, false, offset, run, mi, hi);
531 }
532 return merge(
533 a1 == a ? b : a,
534 a1 == a ? run[lo] - offset : run[lo],
535 a1,
536 a1 == b ? run[lo] - offset : run[lo],
537 a1 == b ? run[mi] - offset : run[mi],
538 a2,
539 a2 == b ? run[mi] - offset : run[mi],
540 a2 == b ? run[hi] - offset : run[hi]);
541 }
542
543 /**
544 * Merges the sorted halves.
545 *
546 * @param dst the destination where halves are merged
547 * @param k the start index of the destination, inclusive
548 * @param a1 the first half
549 * @param i the start index of the first half, inclusive
550 * @param hi the end index of the first half, exclusive
551 * @param a2 the second half
552 * @param j the start index of the second half, inclusive
553 * @param hj the end index of the second half, exclusive
554 * @return the merged halves
555 */
556 private static char[] merge(char[] dst, int k,
557 char[] a1, int i, int hi, char[] a2, int j, int hj) {
558
559 while (true) {
560 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
561
562 if (i == hi) {
563 while (j < hj) {
564 dst[k++] = a2[j++];
565 }
566 return dst;
567 }
568 if (j == hj) {
569 while (i < hi) {
570 dst[k++] = a1[i++];
571 }
572 return dst;
573 }
574 }
575 }
576
577 /**
578 * Tries to sort the specified range of the array by the Merging sort.
579 *
580 * @param a the array to be sorted
581 * @param parallel indicates whether merging is performed in parallel
582 * @param low the index of the first element, inclusive, to be sorted
583 * @param high the index of the last element, exclusive, to be sorted
584 * @return true if the given array is finally sorted, false otherwise
585 */
586 static boolean mergingSort(short[] a, boolean parallel, int low, int high) {
587 int length = high - low;
588
589 if (length < MERGING_SORT_THRESHOLD) {
590 return false;
591 }
592
593 /*
594 * Index run[i] is the start of i-th run.
595 * A run is a subsequence of elements
596 * in ascending or descending order.
597 */
598 int max = getMaxRunCount(length);
599 int[] run = new int[max + 1];
600 int count = 0, last = low; run[0] = low;
601
602 /*
603 * Check if the array is highly structured.
604 */
605 for (int k = low + 1; k < high && count < max; ) {
606 if (a[k - 1] < a[k]) {
607
608 // Identify ascending sequence
609 while (++k < high && a[k - 1] <= a[k]);
610
611 } else if (a[k - 1] > a[k]) {
612
613 // Identify descending sequence
614 while (++k < high && a[k - 1] >= a[k]);
615
616 // Reverse the run into ascending order
617 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
618 short ai = a[i]; a[i] = a[j]; a[j] = ai;
619 }
620 } else { // Sequence with equal elements
621 for (short ak = a[k]; ++k < high && ak == a[k]; );
622
623 if (k < high) {
624 continue;
625 }
626 }
627
628 if (count == 0 || a[last - 1] > a[last]) {
629 ++count;
630 }
631 run[count] = (last = k);
632 }
633
634 if (count < max && count > 1) {
635 /*
636 * The array is highly structured, therefore merge all runs.
637 */
638 merge(a, new short[length], true, parallel, low, run, 0, count);
639 }
640 return count < max;
641 }
642
643 /**
644 * Merges the specified runs.
645 *
646 * @param a the source array
647 * @param b the temporary buffer
648 * @param src specifies the type of the target: source or buffer
649 * @param parallel indicates whether merging is performed in parallel
650 * @param offset the start index of the source, inclusive
651 * @param run the start indexes of the runs, inclusive
652 * @param lo the start index of the first run, inclusive
653 * @param hi the start index of the last run, inclusive
654 * @return the target where runs are merged
655 */
656 private static short[] merge(short[] a, short[] b, boolean src,
657 boolean parallel, int offset, int[] run, int lo, int hi) {
658
659 if (hi - lo == 1) {
660 if (src) {
661 return a;
662 }
663 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
664 b[--j] = a[--i]
665 );
666 return b;
667 }
668 int mi = (lo + hi) >>> 1;
669
670 short[] a1, a2; // the left and the right halves to be merged
671
672 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
673 Merger<short[]> merger1 = new Merger<short[]>(a, b, !src, offset, run, lo, mi);
674 Merger<short[]> merger2 = new Merger<short[]>(a, b, true, offset, run, mi, hi);
675
676 ForkJoinTask.invokeAll(merger1, merger2);
677
678 a1 = merger1.getRawResult();
679 a2 = merger2.getRawResult();
680 } else {
681 a1 = merge(a, b, !src, false, offset, run, lo, mi);
682 a2 = merge(a, b, true, false, offset, run, mi, hi);
683 }
684 return merge(
685 a1 == a ? b : a,
686 a1 == a ? run[lo] - offset : run[lo],
687 a1,
688 a1 == b ? run[lo] - offset : run[lo],
689 a1 == b ? run[mi] - offset : run[mi],
690 a2,
691 a2 == b ? run[mi] - offset : run[mi],
692 a2 == b ? run[hi] - offset : run[hi]);
693 }
694
695 /**
696 * Merges the sorted halves.
697 *
698 * @param dst the destination where halves are merged
699 * @param k the start index of the destination, inclusive
700 * @param a1 the first half
701 * @param i the start index of the first half, inclusive
702 * @param hi the end index of the first half, exclusive
703 * @param a2 the second half
704 * @param j the start index of the second half, inclusive
705 * @param hj the end index of the second half, exclusive
706 * @return the merged halves
707 */
708 private static short[] merge(short[] dst, int k,
709 short[] a1, int i, int hi, short[] a2, int j, int hj) {
710
711 while (true) {
712 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
713
714 if (i == hi) {
715 while (j < hj) {
716 dst[k++] = a2[j++];
717 }
718 return dst;
719 }
720 if (j == hj) {
721 while (i < hi) {
722 dst[k++] = a1[i++];
723 }
724 return dst;
725 }
726 }
727 }
728
729 /**
730 * Tries to sort the specified range of the array by the Merging sort.
731 *
732 * @param a the array to be sorted
733 * @param parallel indicates whether merging is performed in parallel
734 * @param low the index of the first element, inclusive, to be sorted
735 * @param high the index of the last element, exclusive, to be sorted
736 * @return true if the given array is finally sorted, false otherwise
737 */
738 static boolean mergingSort(float[] a, boolean parallel, int low, int high) {
739 int length = high - low;
740
741 if (length < MERGING_SORT_THRESHOLD) {
742 return false;
743 }
744
745 /*
746 * Index run[i] is the start of i-th run.
747 * A run is a subsequence of elements
748 * in ascending or descending order.
749 */
750 int max = getMaxRunCount(length);
751 int[] run = new int[max + 1];
752 int count = 0, last = low; run[0] = low;
753
754 /*
755 * Check if the array is highly structured.
756 */
757 for (int k = low + 1; k < high && count < max; ) {
758 if (a[k - 1] < a[k]) {
759
760 // Identify ascending sequence
761 while (++k < high && a[k - 1] <= a[k]);
762
763 } else if (a[k - 1] > a[k]) {
764
765 // Identify descending sequence
766 while (++k < high && a[k - 1] >= a[k]);
767
768 // Reverse the run into ascending order
769 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
770 float ai = a[i]; a[i] = a[j]; a[j] = ai;
771 }
772 } else { // Sequence with equal elements
773 for (float ak = a[k]; ++k < high && ak == a[k]; );
774
775 if (k < high) {
776 continue;
777 }
778 }
779
780 if (count == 0 || a[last - 1] > a[last]) {
781 ++count;
782 }
783 run[count] = (last = k);
784 }
785
786 if (count < max && count > 1) {
787 /*
788 * The array is highly structured, therefore merge all runs.
789 */
790 merge(a, new float[length], true, parallel, low, run, 0, count);
791 }
792 return count < max;
793 }
794
795 /**
796 * Merges the specified runs.
797 *
798 * @param a the source array
799 * @param b the temporary buffer
800 * @param src specifies the type of the target: source or buffer
801 * @param parallel indicates whether merging is performed in parallel
802 * @param offset the start index of the source, inclusive
803 * @param run the start indexes of the runs, inclusive
804 * @param lo the start index of the first run, inclusive
805 * @param hi the start index of the last run, inclusive
806 * @return the target where runs are merged
807 */
808 private static float[] merge(float[] a, float[] b, boolean src,
809 boolean parallel, int offset, int[] run, int lo, int hi) {
810
811 if (hi - lo == 1) {
812 if (src) {
813 return a;
814 }
815 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
816 b[--j] = a[--i]
817 );
818 return b;
819 }
820 int mi = (lo + hi) >>> 1;
821
822 float[] a1, a2; // the left and the right halves to be merged
823
824 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
825 Merger<float[]> merger1 = new Merger<float[]>(a, b, !src, offset, run, lo, mi);
826 Merger<float[]> merger2 = new Merger<float[]>(a, b, true, offset, run, mi, hi);
827
828 ForkJoinTask.invokeAll(merger1, merger2);
829
830 a1 = merger1.getRawResult();
831 a2 = merger2.getRawResult();
832 } else {
833 a1 = merge(a, b, !src, false, offset, run, lo, mi);
834 a2 = merge(a, b, true, false, offset, run, mi, hi);
835 }
836 return merge(
837 a1 == a ? b : a,
838 a1 == a ? run[lo] - offset : run[lo],
839 a1,
840 a1 == b ? run[lo] - offset : run[lo],
841 a1 == b ? run[mi] - offset : run[mi],
842 a2,
843 a2 == b ? run[mi] - offset : run[mi],
844 a2 == b ? run[hi] - offset : run[hi]);
845 }
846
847 /**
848 * Merges the sorted halves.
849 *
850 * @param dst the destination where halves are merged
851 * @param k the start index of the destination, inclusive
852 * @param a1 the first half
853 * @param i the start index of the first half, inclusive
854 * @param hi the end index of the first half, exclusive
855 * @param a2 the second half
856 * @param j the start index of the second half, inclusive
857 * @param hj the end index of the second half, exclusive
858 * @return the merged halves
859 */
860 private static float[] merge(float[] dst, int k,
861 float[] a1, int i, int hi, float[] a2, int j, int hj) {
862
863 while (true) {
864 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
865
866 if (i == hi) {
867 while (j < hj) {
868 dst[k++] = a2[j++];
869 }
870 return dst;
871 }
872 if (j == hj) {
873 while (i < hi) {
874 dst[k++] = a1[i++];
875 }
876 return dst;
877 }
878 }
879 }
880
881 /**
882 * Tries to sort the specified range of the array by the Merging sort.
883 *
884 * @param a the array to be sorted
885 * @param parallel indicates whether merging is performed in parallel
886 * @param low the index of the first element, inclusive, to be sorted
887 * @param high the index of the last element, exclusive, to be sorted
888 * @return true if the given array is finally sorted, false otherwise
889 */
890 static boolean mergingSort(double[] a, boolean parallel, int low, int high) {
891 int length = high - low;
892
893 if (length < MERGING_SORT_THRESHOLD) {
894 return false;
895 }
896
897 /*
898 * Index run[i] is the start of i-th run.
899 * A run is a subsequence of elements
900 * in ascending or descending order.
901 */
902 int max = getMaxRunCount(length);
903 int[] run = new int[max + 1];
904 int count = 0, last = low; run[0] = low;
905
906 /*
907 * Check if the array is highly structured.
908 */
909 for (int k = low + 1; k < high && count < max; ) {
910 if (a[k - 1] < a[k]) {
911
912 // Identify ascending sequence
913 while (++k < high && a[k - 1] <= a[k]);
914
915 } else if (a[k - 1] > a[k]) {
916
917 // Identify descending sequence
918 while (++k < high && a[k - 1] >= a[k]);
919
920 // Reverse the run into ascending order
921 for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
922 double ai = a[i]; a[i] = a[j]; a[j] = ai;
923 }
924 } else { // Sequence with equal elements
925 for (double ak = a[k]; ++k < high && ak == a[k]; );
926
927 if (k < high) {
928 continue;
929 }
930 }
931
932 if (count == 0 || a[last - 1] > a[last]) {
933 ++count;
934 }
935 run[count] = (last = k);
936 }
937
938 if (count < max && count > 1) {
939 /*
940 * The array is highly structured, therefore merge all runs.
941 */
942 merge(a, new double[length], true, parallel, low, run, 0, count);
943 }
944 return count < max;
945 }
946
947 /**
948 * Merges the specified runs.
949 *
950 * @param a the source array
951 * @param b the temporary buffer
952 * @param src specifies the type of the target: source or buffer
953 * @param parallel indicates whether merging is performed in parallel
954 * @param offset the start index of the source, inclusive
955 * @param run the start indexes of the runs, inclusive
956 * @param lo the start index of the first run, inclusive
957 * @param hi the start index of the last run, inclusive
958 * @return the target where runs are merged
959 */
960 private static double[] merge(double[] a, double[] b, boolean src,
961 boolean parallel, int offset, int[] run, int lo, int hi) {
962
963 if (hi - lo == 1) {
964 if (src) {
965 return a;
966 }
967 for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
968 b[--j] = a[--i]
969 );
970 return b;
971 }
972 int mi = (lo + hi) >>> 1;
973
974 double[] a1, a2; // the left and the right halves to be merged
975
976 if (parallel && hi - lo > MIN_PARALLEL_RUNS_COUNT) {
977 Merger<double[]> merger1 = new Merger<double[]>(a, b, !src, offset, run, lo, mi);
978 Merger<double[]> merger2 = new Merger<double[]>(a, b, true, offset, run, mi, hi);
979
980 ForkJoinTask.invokeAll(merger1, merger2);
981
982 a1 = merger1.getRawResult();
983 a2 = merger2.getRawResult();
984 } else {
985 a1 = merge(a, b, !src, false, offset, run, lo, mi);
986 a2 = merge(a, b, true, false, offset, run, mi, hi);
987 }
988 return merge(
989 a1 == a ? b : a,
990 a1 == a ? run[lo] - offset : run[lo],
991 a1,
992 a1 == b ? run[lo] - offset : run[lo],
993 a1 == b ? run[mi] - offset : run[mi],
994 a2,
995 a2 == b ? run[mi] - offset : run[mi],
996 a2 == b ? run[hi] - offset : run[hi]);
997 }
998
999 /**
1000 * Merges the sorted halves.
1001 *
1002 * @param dst the destination where halves are merged
1003 * @param k the start index of the destination, inclusive
1004 * @param a1 the first half
1005 * @param i the start index of the first half, inclusive
1006 * @param hi the end index of the first half, exclusive
1007 * @param a2 the second half
1008 * @param j the start index of the second half, inclusive
1009 * @param hj the end index of the second half, exclusive
1010 * @return the merged halves
1011 */
1012 private static double[] merge(double[] dst, int k,
1013 double[] a1, int i, int hi, double[] a2, int j, int hj) {
1014
1015 while (true) {
1016 dst[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
1017
1018 if (i == hi) {
1019 while (j < hj) {
1020 dst[k++] = a2[j++];
1021 }
1022 return dst;
1023 }
1024 if (j == hj) {
1025 while (i < hi) {
1026 dst[k++] = a1[i++];
1027 }
1028 return dst;
1029 }
1030 }
1031 }
1032
1033 /**
1034 * Sorts the specified range of the array by the nano insertion sort.
1035 *
1036 * @param a the array to be sorted
1037 * @param low the index of the first element, inclusive, to be sorted
1038 * @param high the index of the last element, exclusive, to be sorted
1039 */
1040 static void nanoInsertionSort(int[] a, int low, int high) {
1041 /*
1042 * In the context of Quicksort, the elements from the left part
1043 * play the role of sentinels. Therefore expensive check of the
1044 * left range on each iteration can be skipped.
1045 */
1046 for (int k; ++low < high; ) {
1047 int ak = a[k = low];
1048
1049 while (ak < a[--k]) {
1050 a[k + 1] = a[k];
1051 }
1052 a[k + 1] = ak;
1053 }
1054 }
1055
1056 /**
1057 * Sorts the specified range of the array by the nano insertion sort.
1058 *
1059 * @param a the array to be sorted
1060 * @param low the index of the first element, inclusive, to be sorted
1061 * @param high the index of the last element, exclusive, to be sorted
1062 */
1063 static void nanoInsertionSort(long[] a, int low, int high) {
1064 /*
1065 * In the context of Quicksort, the elements from the left part
1066 * play the role of sentinels. Therefore expensive check of the
1067 * left range on each iteration can be skipped.
1068 */
1069 for (int k; ++low < high; ) {
1070 long ak = a[k = low];
1071
1072 while (ak < a[--k]) {
1073 a[k + 1] = a[k];
1074 }
1075 a[k + 1] = ak;
1076 }
1077 }
1078
1079 /**
1080 * Sorts the specified range of the array by the nano insertion sort.
1081 *
1082 * @param a the array to be sorted
1083 * @param low the index of the first element, inclusive, to be sorted
1084 * @param high the index of the last element, exclusive, to be sorted
1085 */
1086 static void nanoInsertionSort(char[] a, int low, int high) {
1087 /*
1088 * In the context of Quicksort, the elements from the left part
1089 * play the role of sentinels. Therefore expensive check of the
1090 * left range on each iteration can be skipped.
1091 */
1092 for (int k; ++low < high; ) {
1093 char ak = a[k = low];
1094
1095 while (ak < a[--k]) {
1096 a[k + 1] = a[k];
1097 }
1098 a[k + 1] = ak;
1099 }
1100 }
1101
1102 /**
1103 * Sorts the specified range of the array by the nano insertion sort.
1104 *
1105 * @param a the array to be sorted
1106 * @param low the index of the first element, inclusive, to be sorted
1107 * @param high the index of the last element, exclusive, to be sorted
1108 */
1109 static void nanoInsertionSort(short[] a, int low, int high) {
1110 /*
1111 * In the context of Quicksort, the elements from the left part
1112 * play the role of sentinels. Therefore expensive check of the
1113 * left range on each iteration can be skipped.
1114 */
1115 for (int k; ++low < high; ) {
1116 short ak = a[k = low];
1117
1118 while (ak < a[--k]) {
1119 a[k + 1] = a[k];
1120 }
1121 a[k + 1] = ak;
1122 }
1123 }
1124
1125 /**
1126 * Sorts the specified range of the array by the nano insertion sort.
1127 *
1128 * @param a the array to be sorted
1129 * @param low the index of the first element, inclusive, to be sorted
1130 * @param high the index of the last element, exclusive, to be sorted
1131 */
1132 static void nanoInsertionSort(float[] a, int low, int high) {
1133 /*
1134 * In the context of Quicksort, the elements from the left part
1135 * play the role of sentinels. Therefore expensive check of the
1136 * left range on each iteration can be skipped.
1137 */
1138 for (int k; ++low < high; ) {
1139 float ak = a[k = low];
1140
1141 while (ak < a[--k]) {
1142 a[k + 1] = a[k];
1143 }
1144 a[k + 1] = ak;
1145 }
1146 }
1147
1148 /**
1149 * Sorts the specified range of the array by the nano insertion sort.
1150 *
1151 * @param a the array to be sorted
1152 * @param low the index of the first element, inclusive, to be sorted
1153 * @param high the index of the last element, exclusive, to be sorted
1154 */
1155 static void nanoInsertionSort(double[] a, int low, int high) {
1156 /*
1157 * In the context of Quicksort, the elements from the left part
1158 * play the role of sentinels. Therefore expensive check of the
1159 * left range on each iteration can be skipped.
1160 */
1161 for (int k; ++low < high; ) {
1162 double ak = a[k = low];
1163
1164 while (ak < a[--k]) {
1165 a[k + 1] = a[k];
1166 }
1167 a[k + 1] = ak;
1168 }
1169 }
1170
1171 /**
1172 * Sorts the specified range of the array by the pair insertion sort.
1173 *
1174 * @param a the array to be sorted
1175 * @param left the index of the first element, inclusive, to be sorted
1176 * @param right the index of the last element, inclusive, to be sorted
1177 */
1178 static void pairInsertionSort(int[] a, int left, int right) {
1179 /*
1180 * Allign the left boundary.
1181 */
1182 left -= (left ^ right) & 1;
1183
1184 /*
1185 * Two elements are inserted at once on each iteration.
1186 * At first, we insert the greater element (a2) and then
1187 * insert the less element (a1), but from position where
1188 * the greater element was inserted. In the context of a
1189 * Dual-Pivot Quicksort, the elements from the left part
1190 * play the role of sentinels. Therefore expensive check
1191 * of the left range on each iteration can be skipped.
1192 */
1193 for (int k; ++left < right; ) {
1194 int a1 = a[k = ++left];
1195
1196 if (a[k - 2] > a[k - 1]) {
1197 int a2 = a[--k];
1198
1199 if (a1 > a2) {
1200 a2 = a1; a1 = a[k];
1201 }
1202 while (a2 < a[--k]) {
1203 a[k + 2] = a[k];
1204 }
1205 a[++k + 1] = a2;
1206 }
1207 while (a1 < a[--k]) {
1208 a[k + 1] = a[k];
1209 }
1210 a[k + 1] = a1;
1211 }
1212 }
1213
1214 /**
1215 * Sorts the specified range of the array by the pair insertion sort.
1216 *
1217 * @param a the array to be sorted
1218 * @param left the index of the first element, inclusive, to be sorted
1219 * @param right the index of the last element, inclusive, to be sorted
1220 */
1221 static void pairInsertionSort(long[] a, int left, int right) {
1222 /*
1223 * Allign the left boundary.
1224 */
1225 left -= (left ^ right) & 1;
1226
1227 /*
1228 * Two elements are inserted at once on each iteration.
1229 * At first, we insert the greater element (a2) and then
1230 * insert the less element (a1), but from position where
1231 * the greater element was inserted. In the context of a
1232 * Dual-Pivot Quicksort, the elements from the left part
1233 * play the role of sentinels. Therefore expensive check
1234 * of the left range on each iteration can be skipped.
1235 */
1236 for (int k; ++left < right; ) {
1237 long a1 = a[k = ++left];
1238
1239 if (a[k - 2] > a[k - 1]) {
1240 long a2 = a[--k];
1241
1242 if (a1 > a2) {
1243 a2 = a1; a1 = a[k];
1244 }
1245 while (a2 < a[--k]) {
1246 a[k + 2] = a[k];
1247 }
1248 a[++k + 1] = a2;
1249 }
1250 while (a1 < a[--k]) {
1251 a[k + 1] = a[k];
1252 }
1253 a[k + 1] = a1;
1254 }
1255 }
1256
1257 /**
1258 * Sorts the specified range of the array by the pair insertion sort.
1259 *
1260 * @param a the array to be sorted
1261 * @param left the index of the first element, inclusive, to be sorted
1262 * @param right the index of the last element, inclusive, to be sorted
1263 */
1264 static void pairInsertionSort(char[] a, int left, int right) {
1265 /*
1266 * Allign the left boundary.
1267 */
1268 left -= (left ^ right) & 1;
1269
1270 /*
1271 * Two elements are inserted at once on each iteration.
1272 * At first, we insert the greater element (a2) and then
1273 * insert the less element (a1), but from position where
1274 * the greater element was inserted. In the context of a
1275 * Dual-Pivot Quicksort, the elements from the left part
1276 * play the role of sentinels. Therefore expensive check
1277 * of the left range on each iteration can be skipped.
1278 */
1279 for (int k; ++left < right; ) {
1280 char a1 = a[k = ++left];
1281
1282 if (a[k - 2] > a[k - 1]) {
1283 char a2 = a[--k];
1284
1285 if (a1 > a2) {
1286 a2 = a1; a1 = a[k];
1287 }
1288 while (a2 < a[--k]) {
1289 a[k + 2] = a[k];
1290 }
1291 a[++k + 1] = a2;
1292 }
1293 while (a1 < a[--k]) {
1294 a[k + 1] = a[k];
1295 }
1296 a[k + 1] = a1;
1297 }
1298 }
1299
1300 /**
1301 * Sorts the specified range of the array by the pair insertion sort.
1302 *
1303 * @param a the array to be sorted
1304 * @param left the index of the first element, inclusive, to be sorted
1305 * @param right the index of the last element, inclusive, to be sorted
1306 */
1307 static void pairInsertionSort(short[] a, int left, int right) {
1308 /*
1309 * Allign the left boundary.
1310 */
1311 left -= (left ^ right) & 1;
1312
1313 /*
1314 * Two elements are inserted at once on each iteration.
1315 * At first, we insert the greater element (a2) and then
1316 * insert the less element (a1), but from position where
1317 * the greater element was inserted. In the context of a
1318 * Dual-Pivot Quicksort, the elements from the left part
1319 * play the role of sentinels. Therefore expensive check
1320 * of the left range on each iteration can be skipped.
1321 */
1322 for (int k; ++left < right; ) {
1323 short a1 = a[k = ++left];
1324
1325 if (a[k - 2] > a[k - 1]) {
1326 short a2 = a[--k];
1327
1328 if (a1 > a2) {
1329 a2 = a1; a1 = a[k];
1330 }
1331 while (a2 < a[--k]) {
1332 a[k + 2] = a[k];
1333 }
1334 a[++k + 1] = a2;
1335 }
1336 while (a1 < a[--k]) {
1337 a[k + 1] = a[k];
1338 }
1339 a[k + 1] = a1;
1340 }
1341 }
1342
1343 /**
1344 * Sorts the specified range of the array by the pair insertion sort.
1345 *
1346 * @param a the array to be sorted
1347 * @param left the index of the first element, inclusive, to be sorted
1348 * @param right the index of the last element, inclusive, to be sorted
1349 */
1350 static void pairInsertionSort(float[] a, int left, int right) {
1351 /*
1352 * Allign the left boundary.
1353 */
1354 left -= (left ^ right) & 1;
1355
1356 /*
1357 * Two elements are inserted at once on each iteration.
1358 * At first, we insert the greater element (a2) and then
1359 * insert the less element (a1), but from position where
1360 * the greater element was inserted. In the context of a
1361 * Dual-Pivot Quicksort, the elements from the left part
1362 * play the role of sentinels. Therefore expensive check
1363 * of the left range on each iteration can be skipped.
1364 */
1365 for (int k; ++left < right; ) {
1366 float a1 = a[k = ++left];
1367
1368 if (a[k - 2] > a[k - 1]) {
1369 float a2 = a[--k];
1370
1371 if (a1 > a2) {
1372 a2 = a1; a1 = a[k];
1373 }
1374 while (a2 < a[--k]) {
1375 a[k + 2] = a[k];
1376 }
1377 a[++k + 1] = a2;
1378 }
1379 while (a1 < a[--k]) {
1380 a[k + 1] = a[k];
1381 }
1382 a[k + 1] = a1;
1383 }
1384 }
1385
1386 /**
1387 * Sorts the specified range of the array by the pair insertion sort.
1388 *
1389 * @param a the array to be sorted
1390 * @param left the index of the first element, inclusive, to be sorted
1391 * @param right the index of the last element, inclusive, to be sorted
1392 */
1393 static void pairInsertionSort(double[] a, int left, int right) {
1394 /*
1395 * Allign the left boundary.
1396 */
1397 left -= (left ^ right) & 1;
1398
1399 /*
1400 * Two elements are inserted at once on each iteration.
1401 * At first, we insert the greater element (a2) and then
1402 * insert the less element (a1), but from position where
1403 * the greater element was inserted. In the context of a
1404 * Dual-Pivot Quicksort, the elements from the left part
1405 * play the role of sentinels. Therefore expensive check
1406 * of the left range on each iteration can be skipped.
1407 */
1408 for (int k; ++left < right; ) {
1409 double a1 = a[k = ++left];
1410
1411 if (a[k - 2] > a[k - 1]) {
1412 double a2 = a[--k];
1413
1414 if (a1 > a2) {
1415 a2 = a1; a1 = a[k];
1416 }
1417 while (a2 < a[--k]) {
1418 a[k + 2] = a[k];
1419 }
1420 a[++k + 1] = a2;
1421 }
1422 while (a1 < a[--k]) {
1423 a[k + 1] = a[k];
1424 }
1425 a[k + 1] = a1;
1426 }
1427 }
1428
1429 /**
1430 * Sorts the specified range of the array by optimized insertion sort.
1431 *
1432 * @param a the array to be sorted
1433 * @param low the index of the first element, inclusive, to be sorted
1434 * @param high the index of the last element, exclusive, to be sorted
1435 */
1436 static void insertionSort(byte[] a, int low, int high) {
1437 for (int i, k = low; ++k < high; ) {
1438 byte ak = a[i = k];
1439
1440 if (ak < a[low]) {
1441 a[i] = a[low]; a[low] = ak; ak = a[i];
1442 }
1443 while (ak < a[--i]) {
1444 a[i + 1] = a[i];
1445 }
1446 a[i + 1] = ak;
1447 }
1448 }
1449
1450 /**
1451 * The number of distinct byte values.
1452 */
1453 private static final int NUM_BYTE_VALUES = 1 << 8;
1454
1455 /**
1456 * Sorts the specified range of the array by the counting sort.
1457 *
1458 * @param a the array to be sorted
1459 * @param low the index of the first element, inclusive, to be sorted
1460 * @param high the index of the last element, exclusive, to be sorted
1461 */
1462 static void countingSort(byte[] a, int low, int high) {
1463 int[] count = new int[NUM_BYTE_VALUES];
1464
1465 /*
1466 * Compute a histogram with the number of each values.
1467 */
1468 for (int i = low; i < high; ++i) {
1469 ++count[a[i] - Byte.MIN_VALUE];
1470 }
1471
1472 /*
1473 * Place values on their final positions.
1474 */
1475 for (int i = NUM_BYTE_VALUES, k = high; k > low; ) {
1476 while (count[--i] == 0);
1477 byte value = (byte) (i + Byte.MIN_VALUE);
1478 for (int j = count[i]; --j >= 0; a[--k] = value);
1479 }
1480 }
1481
1482 /**
1483 * The number of distinct char values.
1484 */
1485 private static final int NUM_CHAR_VALUES = 1 << 16;
1486
1487 /**
1488 * Sorts the specified range of the array by the counting sort.
1489 *
1490 * @param a the array to be sorted
1491 * @param low the index of the first element, inclusive, to be sorted
1492 * @param high the index of the last element, exclusive, to be sorted
1493 */
1494 static void countingSort(char[] a, int low, int high) {
1495 int[] count = new int[NUM_CHAR_VALUES];
1496
1497 /*
1498 * Compute a histogram with the number of each values.
1499 */
1500 for (int i = low; i < high; ++i) {
1501 ++count[a[i]];
1502 }
1503
1504 /*
1505 * Place values on their final positions.
1506 */
1507 for (int i = NUM_CHAR_VALUES, k = high; k > low; ) {
1508 while (count[--i] == 0);
1509 char value = (char) i;
1510 for (int j = count[i]; --j >= 0; a[--k] = value);
1511 }
1512 }
1513
1514 /**
1515 * The number of distinct short values.
1516 */
1517 private static final int NUM_SHORT_VALUES = 1 << 16;
1518
1519 /**
1520 * Sorts the specified range of the array by the counting sort.
1521 *
1522 * @param a the array to be sorted
1523 * @param low the index of the first element, inclusive, to be sorted
1524 * @param high the index of the last element, exclusive, to be sorted
1525 */
1526 static void countingSort(short[] a, int low, int high) {
1527 int[] count = new int[NUM_SHORT_VALUES];
1528
1529 /*
1530 * Compute a histogram with the number of each values.
1531 */
1532 for (int i = low; i < high; ++i) {
1533 ++count[a[i] - Short.MIN_VALUE];
1534 }
1535
1536 /*
1537 * Place values on their final positions.
1538 */
1539 for (int i = NUM_SHORT_VALUES, k = high; k > low; ) {
1540 while (count[--i] == 0);
1541 short value = (short) (i + Short.MIN_VALUE);
1542 for (int j = count[i]; --j >= 0; a[--k] = value);
1543 }
1544 }
1545
1546 /**
1547 * Sorts the specified range of the array by the heap sort.
1548 *
1549 * @param a the array to be sorted
1550 * @param left the index of the first element, inclusive, to be sorted
1551 * @param right the index of the last element, inclusive, to be sorted
1552 */
1553 static void heapSort(int[] a, int left, int right) {
1554 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1555 pushDown(a, --k, a[k], left, right);
1556 }
1557 for (int k = right; k > left; --k) {
1558 int max = a[left];
1559 pushDown(a, left, a[k], left, k);
1560 a[k] = max;
1561 }
1562 }
1563
1564 /**
1565 * Pushes specified element down during the heap sort.
1566 *
1567 * @param a the given array
1568 * @param p the start index
1569 * @param value the given element
1570 * @param left the index of the first element, inclusive, to be sorted
1571 * @param right the index of the last element, inclusive, to be sorted
1572 */
1573 private static void pushDown(int[] a, int p, int value, int left, int right) {
1574 for (int k ;; a[p] = a[p = k]) {
1575 k = (p << 1) - left + 2; // the index of the right child
1576
1577 if (k > right || a[k - 1] > a[k]) {
1578 --k;
1579 }
1580 if (k > right || a[k] <= value) {
1581 a[p] = value;
1582 return;
1583 }
1584 }
1585 }
1586
1587 /**
1588 * Sorts the specified range of the array by the heap sort.
1589 *
1590 * @param a the array to be sorted
1591 * @param left the index of the first element, inclusive, to be sorted
1592 * @param right the index of the last element, inclusive, to be sorted
1593 */
1594 static void heapSort(long[] a, int left, int right) {
1595 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1596 pushDown(a, --k, a[k], left, right);
1597 }
1598 for (int k = right; k > left; --k) {
1599 long max = a[left];
1600 pushDown(a, left, a[k], left, k);
1601 a[k] = max;
1602 }
1603 }
1604
1605 /**
1606 * Pushes specified element down during the heap sort.
1607 *
1608 * @param a the given array
1609 * @param p the start index
1610 * @param value the given element
1611 * @param left the index of the first element, inclusive, to be sorted
1612 * @param right the index of the last element, inclusive, to be sorted
1613 */
1614 private static void pushDown(long[] a, int p, long value, int left, int right) {
1615 for (int k ;; a[p] = a[p = k]) {
1616 k = (p << 1) - left + 2; // the index of the right child
1617
1618 if (k > right || a[k - 1] > a[k]) {
1619 --k;
1620 }
1621 if (k > right || a[k] <= value) {
1622 a[p] = value;
1623 return;
1624 }
1625 }
1626 }
1627
1628 /**
1629 * Sorts the specified range of the array by the heap sort.
1630 *
1631 * @param a the array to be sorted
1632 * @param left the index of the first element, inclusive, to be sorted
1633 * @param right the index of the last element, inclusive, to be sorted
1634 */
1635 static void heapSort(char[] a, int left, int right) {
1636 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1637 pushDown(a, --k, a[k], left, right);
1638 }
1639 for (int k = right; k > left; --k) {
1640 char max = a[left];
1641 pushDown(a, left, a[k], left, k);
1642 a[k] = max;
1643 }
1644 }
1645
1646 /**
1647 * Pushes specified element down during the heap sort.
1648 *
1649 * @param a the given array
1650 * @param p the start index
1651 * @param value the given element
1652 * @param left the index of the first element, inclusive, to be sorted
1653 * @param right the index of the last element, inclusive, to be sorted
1654 */
1655 private static void pushDown(char[] a, int p, char value, int left, int right) {
1656 for (int k ;; a[p] = a[p = k]) {
1657 k = (p << 1) - left + 2; // the index of the right child
1658
1659 if (k > right || a[k - 1] > a[k]) {
1660 --k;
1661 }
1662 if (k > right || a[k] <= value) {
1663 a[p] = value;
1664 return;
1665 }
1666 }
1667 }
1668
1669 /**
1670 * Sorts the specified range of the array by the heap sort.
1671 *
1672 * @param a the array to be sorted
1673 * @param left the index of the first element, inclusive, to be sorted
1674 * @param right the index of the last element, inclusive, to be sorted
1675 */
1676 static void heapSort(short[] a, int left, int right) {
1677 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1678 pushDown(a, --k, a[k], left, right);
1679 }
1680 for (int k = right; k > left; --k) {
1681 short max = a[left];
1682 pushDown(a, left, a[k], left, k);
1683 a[k] = max;
1684 }
1685 }
1686
1687 /**
1688 * Pushes specified element down during the heap sort.
1689 *
1690 * @param a the given array
1691 * @param p the start index
1692 * @param value the given element
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 */
1696 private static void pushDown(short[] a, int p, short value, int left, int right) {
1697 for (int k ;; a[p] = a[p = k]) {
1698 k = (p << 1) - left + 2; // the index of the right child
1699
1700 if (k > right || a[k - 1] > a[k]) {
1701 --k;
1702 }
1703 if (k > right || a[k] <= value) {
1704 a[p] = value;
1705 return;
1706 }
1707 }
1708 }
1709
1710 /**
1711 * Sorts the specified range of the array by the heap sort.
1712 *
1713 * @param a the array to be sorted
1714 * @param left the index of the first element, inclusive, to be sorted
1715 * @param right the index of the last element, inclusive, to be sorted
1716 */
1717 static void heapSort(float[] a, int left, int right) {
1718 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1719 pushDown(a, --k, a[k], left, right);
1720 }
1721 for (int k = right; k > left; --k) {
1722 float max = a[left];
1723 pushDown(a, left, a[k], left, k);
1724 a[k] = max;
1725 }
1726 }
1727
1728 /**
1729 * Pushes specified element down during the heap sort.
1730 *
1731 * @param a the given array
1732 * @param p the start index
1733 * @param value the given element
1734 * @param left the index of the first element, inclusive, to be sorted
1735 * @param right the index of the last element, inclusive, to be sorted
1736 */
1737 private static void pushDown(float[] a, int p, float value, int left, int right) {
1738 for (int k ;; a[p] = a[p = k]) {
1739 k = (p << 1) - left + 2; // the index of the right child
1740
1741 if (k > right || a[k - 1] > a[k]) {
1742 --k;
1743 }
1744 if (k > right || a[k] <= value) {
1745 a[p] = value;
1746 return;
1747 }
1748 }
1749 }
1750
1751 /**
1752 * Sorts the specified range of the array by the heap sort.
1753 *
1754 * @param a the array to be sorted
1755 * @param left the index of the first element, inclusive, to be sorted
1756 * @param right the index of the last element, inclusive, to be sorted
1757 */
1758 static void heapSort(double[] a, int left, int right) {
1759 for (int k = (left + 1 + right) >>> 1; k > left; ) {
1760 pushDown(a, --k, a[k], left, right);
1761 }
1762 for (int k = right; k > left; --k) {
1763 double max = a[left];
1764 pushDown(a, left, a[k], left, k);
1765 a[k] = max;
1766 }
1767 }
1768
1769 /**
1770 * Pushes specified element down during the heap sort.
1771 *
1772 * @param a the given array
1773 * @param p the start index
1774 * @param value the given element
1775 * @param left the index of the first element, inclusive, to be sorted
1776 * @param right the index of the last element, inclusive, to be sorted
1777 */
1778 private static void pushDown(double[] a, int p, double value, int left, int right) {
1779 for (int k ;; a[p] = a[p = k]) {
1780 k = (p << 1) - left + 2; // the index of the right child
1781
1782 if (k > right || a[k - 1] > a[k]) {
1783 --k;
1784 }
1785 if (k > right || a[k] <= value) {
1786 a[p] = value;
1787 return;
1788 }
1789 }
1790 }
1791 }