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