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 }