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