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 */ DualPivotQuicksort()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 */ sort(int[] a, int left, int right, int[] work, int workBase, int workLen)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 */ sort(int[] a, int left, int right, boolean leftmost)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 */ sort(long[] a, int left, int right, long[] work, int workBase, int workLen)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 */ sort(long[] a, int left, int right, boolean leftmost)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 */ sort(short[] a, int left, int right, short[] work, int workBase, int workLen)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 */ doSort(short[] a, int left, int right, short[] work, int workBase, int workLen)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 */ sort(short[] a, int left, int right, boolean leftmost)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 */ sort(char[] a, int left, int right, char[] work, int workBase, int workLen)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 */ doSort(char[] a, int left, int right, char[] work, int workBase, int workLen)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 */ sort(char[] a, int left, int right, boolean leftmost)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 */ sort(byte[] a, int left, int right)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 */ sort(float[] a, int left, int right, float[] work, int workBase, int workLen)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 */ doSort(float[] a, int left, int right, float[] work, int workBase, int workLen)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 */ sort(float[] a, int left, int right, boolean leftmost)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 */ sort(double[] a, int left, int right, double[] work, int workBase, int workLen)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 */ doSort(double[] a, int left, int right, double[] work, int workBase, int workLen)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 */ sort(double[] a, int left, int right, boolean leftmost)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 } 3182