1 /* 2 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.util.concurrent.ForkJoinTask; 29 import java.util.concurrent.RecursiveAction; 30 31 /** 32 * This class implements powerful and fully optimized versions, both 33 * sequential and parallel, of the Dual-Pivot Quicksort algorithm by 34 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm 35 * offers O(n log(n)) performance on all data sets, and is typically 36 * faster than traditional (one-pivot) Quicksort implementations. 37 * 38 * @author Vladimir Yaroslavskiy 39 * @author Jon Bentley 40 * @author Josh Bloch 41 * 42 * @version 2018.02.18 43 * @since 1.7 44 */ 45 final class DualPivotQuicksort { 46 47 /** 48 * Prevents instantiation. 49 */ 50 private DualPivotQuicksort() {} 51 52 /** 53 * If the length of the leftmost part to be sorted is less than 54 * this constant, heap sort is used in preference to Quicksort. 55 */ 56 private static final int HEAP_SORT_THRESHOLD = 69; 57 58 /** 59 * If the length of non-leftmost part to be sorted is less than this 60 * constant, nano insertion sort is used in preference to Quicksort. 61 */ 62 private static final int NANO_INSERTION_SORT_THRESHOLD = 36; 63 64 /** 65 * If the length of non-leftmost part to be sorted is less than this 66 * constant, pair insertion sort is used in preference to Quicksort. 67 */ 68 private static final int PAIR_INSERTION_SORT_THRESHOLD = 88; 69 70 /** 71 * The minimal length of an array, required by parallel Quicksort. 72 */ 73 private static final int PARALLEL_QUICKSORT_THRESHOLD = 1024; 74 75 /** 76 * If the length of a byte array to be sorted is greater than this 77 * constant, counting sort is used in preference to insertion sort. 78 */ 79 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 41; 80 81 /** 82 * If the length of a short or char array to be sorted is greater 83 * than this constant, counting sort is used in preference to Quicksort. 84 */ 85 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 2180; 86 87 /** 88 * if the depth of the Quicksort recursion exceeds this 89 * constant, heap sort is used in preference to Quicksort. 90 */ 91 private static final int MAX_RECURSION_DEPTH = 100; 92 93 /** 94 * This constant is combination of maximum Quicksort recursion depth 95 * and binary flag, where the right bit "0" indicates that the whole 96 * array is considered as the leftmost part. 97 */ 98 private static final int LEFTMOST_BITS = MAX_RECURSION_DEPTH << 1; 99 100 /** 101 * This class implements the parallel Dual-Pivot Quicksort. 102 */ 103 @SuppressWarnings("serial") 104 private static class Sorter<T> extends RecursiveAction { 105 106 Sorter(T a, int bits, int low, int high) { 107 this.a = a; 108 this.bits = bits; 109 this.low = low; 110 this.high = high; 111 } 112 113 @Override 114 protected void compute() { 115 Class<?> clazz = a.getClass(); 116 117 if (clazz == int[].class) { 118 sort((int[]) a, bits, true, low, high); 119 } else if (clazz == long[].class) { 120 sort((long[]) a, bits, true, low, high); 121 } else if (clazz == char[].class) { 122 sort((char[]) a, bits, true, low, high); 123 } else if (clazz == short[].class) { 124 sort((short[]) a, bits, true, low, high); 125 } else if (clazz == float[].class) { 126 sort((float[]) a, bits, true, low, high); 127 } else if (clazz == double[].class) { 128 sort((double[]) a, bits, true, low, high); 129 } else { 130 throw new IllegalArgumentException( 131 "Unknown type of array: " + clazz.getName()); 132 } 133 } 134 135 private T a; 136 private int bits; 137 private int low; 138 private int high; 139 } 140 141 /** 142 * Sorts the specified range of the array. 143 * 144 * @param a the array to be sorted 145 * @param parallel indicates whether sorting is performed in parallel 146 * @param low the index of the first element, inclusive, to be sorted 147 * @param high the index of the last element, exclusive, to be sorted 148 */ 149 static void sort(int[] a, boolean parallel, int low, int high) { 150 sort(a, LEFTMOST_BITS, parallel, low, high); 151 } 152 153 /** 154 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 155 * 156 * @param a the array to be sorted 157 * @param bits the recursion depth of Quicksort and the leftmost flag 158 * @param parallel indicates whether sorting is performed in parallel 159 * @param low the index of the first element, inclusive, to be sorted 160 * @param high the index of the last element, exclusive, to be sorted 161 */ 162 private static void sort(int[] a, int bits, boolean parallel, int low, int high) { 163 int end = high - 1, length = high - low; 164 165 /* 166 * Run insertion sorts on non-leftmost part. 167 */ 168 if ((bits & 1) > 0) { 169 170 /* 171 * Use nano insertion sort on tiny part. 172 */ 173 if (length < NANO_INSERTION_SORT_THRESHOLD) { 174 SortingAlgorithms.nanoInsertionSort(a, low, high); 175 return; 176 } 177 178 /* 179 * Use pair insertion sort on small part. 180 */ 181 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 182 SortingAlgorithms.pairInsertionSort(a, low, end); 183 return; 184 } 185 } 186 187 /* 188 * Switch to heap sort on the leftmost part or 189 * if the execution time is becoming quadratic. 190 */ 191 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 192 SortingAlgorithms.heapSort(a, low, end); 193 return; 194 } 195 196 /* 197 * Check if the array is nearly sorted 198 * and then try to sort it by Merging sort. 199 */ 200 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 201 return; 202 } 203 204 /* 205 * The splitting of the array, defined by the following 206 * step, is related to the inexpensive approximation of 207 * the golden ratio. 208 */ 209 int step = (length >> 3) * 3 + 3; 210 211 /* 212 * Five elements around (and including) the central element in 213 * the array will be used for pivot selection as described below. 214 * The unequal choice of spacing these elements was empirically 215 * determined to work well on a wide variety of inputs. 216 */ 217 int e1 = low + step; 218 int e5 = end - step; 219 int e3 = (e1 + e5) >>> 1; 220 int e2 = (e1 + e3) >>> 1; 221 int e4 = (e3 + e5) >>> 1; 222 223 /* 224 * Sort these elements in place by the combination 225 * of 5-element sorting network and insertion sort. 226 */ 227 if (a[e5] < a[e3]) { int t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 228 if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 229 if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 230 if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 231 if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 232 233 if (a[e1] > a[e2]) { int t = a[e1]; a[e1] = a[e2]; a[e2] = t; 234 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 235 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 236 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 237 } 238 } 239 } 240 241 // Pointers 242 int lower = low; // The index of the last element of the left part 243 int upper = end; // The index of the first element of the right part 244 245 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 246 247 /* 248 * Use the first and the fifth elements as the pivots. 249 * These values are inexpensive approximation of tertiles. 250 * Note, that pivot1 < pivot2. 251 */ 252 int pivot1 = a[e1]; 253 int pivot2 = a[e5]; 254 255 /* 256 * The first and the last elements to be sorted are moved to the 257 * locations formerly occupied by the pivots. When partitioning 258 * is completed, the pivots are swapped back into their final 259 * positions, and excluded from subsequent sorting. 260 */ 261 a[e1] = a[lower]; 262 a[e5] = a[upper]; 263 264 /* 265 * Skip elements, which are less or greater than the pivots. 266 */ 267 while (a[++lower] < pivot1); 268 while (a[--upper] > pivot2); 269 270 /* 271 * Backwards 3-interval partitioning 272 * 273 * left part central part right part 274 * +------------------------------------------------------------+ 275 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 276 * +------------------------------------------------------------+ 277 * ^ ^ ^ 278 * | | | 279 * lower k upper 280 * 281 * Invariants: 282 * 283 * all in (low, lower] < pivot1 284 * pivot1 <= all in (k, upper) <= pivot2 285 * all in [upper, end) > pivot2 286 * 287 * Pointer k is the last index of ?-part 288 */ 289 for (int $ = --lower, k = ++upper; --k > lower; ) { 290 int ak = a[k]; 291 292 if (ak < pivot1) { // Move a[k] to the left side 293 while (a[++lower] < pivot1); 294 295 if (lower > k) { 296 lower = k; 297 break; 298 } 299 if (a[lower] > pivot2) { // a[lower] >= pivot1 300 a[k] = a[--upper]; 301 a[upper] = a[lower]; 302 } else { // pivot1 <= a[lower] <= pivot2 303 a[k] = a[lower]; 304 } 305 a[lower] = ak; 306 } else if (ak > pivot2) { // Move a[k] to the right side 307 a[k] = a[--upper]; 308 a[upper] = ak; 309 } 310 } 311 312 /* 313 * Swap the pivots into their final positions. 314 */ 315 a[low] = a[lower]; a[lower] = pivot1; 316 a[end] = a[upper]; a[upper] = pivot2; 317 318 /* 319 * Sort all parts recursively, excluding known pivots. 320 */ 321 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 322 ForkJoinTask.invokeAll( 323 new Sorter<int[]>(a, bits | 1, lower + 1, upper), 324 new Sorter<int[]>(a, bits | 1, upper + 1, high), 325 new Sorter<int[]>(a, bits, low, lower) 326 ); 327 } else { 328 sort(a, bits | 1, false, upper + 1, high); 329 sort(a, bits, false, low, lower); 330 sort(a, bits | 1, false, lower + 1, upper); 331 } 332 } else { // Partitioning with one pivot 333 334 /* 335 * Use the third element as the pivot. This value 336 * is inexpensive approximation of the median. 337 */ 338 int pivot = a[e3]; 339 340 /* 341 * The first element to be sorted is moved to the location 342 * formerly occupied by the pivot. When partitioning is 343 * completed, the pivot is swapped back into its final 344 * position, and excluded from subsequent sorting. 345 */ 346 a[e3] = a[lower]; 347 348 /* 349 * Traditional 3-way (Dutch National Flag) partitioning 350 * 351 * left part central part right part 352 * +------------------------------------------------------+ 353 * | < pivot | ? | == pivot | > pivot | 354 * +------------------------------------------------------+ 355 * ^ ^ ^ 356 * | | | 357 * lower k upper 358 * 359 * Invariants: 360 * 361 * all in (low, lower] < pivot 362 * all in (k, upper) == pivot 363 * all in [upper, end] > pivot 364 * 365 * Pointer k is the last index of ?-part 366 */ 367 for (int k = ++upper; --k > lower; ) { 368 if (a[k] == pivot) { 369 continue; 370 } 371 int ak = a[k]; 372 373 if (ak < pivot) { // Move a[k] to the left side 374 while (a[++lower] < pivot); 375 376 if (lower > k) { 377 lower = k; 378 break; 379 } 380 a[k] = pivot; 381 382 if (a[lower] > pivot) { 383 a[--upper] = a[lower]; 384 } 385 a[lower] = ak; 386 } else { // ak > pivot - Move a[k] to the right side 387 a[k] = pivot; 388 a[--upper] = ak; 389 } 390 } 391 392 /* 393 * Swap the pivot into its final position. 394 */ 395 a[low] = a[lower]; a[lower] = pivot; 396 397 /* 398 * Sort the left and the right parts recursively, excluding 399 * known pivot. All elements from the central part are equal 400 * and, therefore, already sorted. 401 */ 402 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 403 ForkJoinTask.invokeAll( 404 new Sorter<int[]>(a, bits, low, lower), 405 new Sorter<int[]>(a, bits | 1, upper, high) 406 ); 407 } else { 408 sort(a, bits | 1, false, upper, high); 409 sort(a, bits, false, low, lower); 410 } 411 } 412 } 413 414 /** 415 * Sorts the specified range of the array. 416 * 417 * @param a the array to be sorted 418 * @param parallel indicates whether sorting is performed in parallel 419 * @param low the index of the first element, inclusive, to be sorted 420 * @param high the index of the last element, exclusive, to be sorted 421 */ 422 static void sort(long[] a, boolean parallel, int low, int high) { 423 sort(a, LEFTMOST_BITS, parallel, low, high); 424 } 425 426 /** 427 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 428 * 429 * @param a the array to be sorted 430 * @param bits the recursion depth of Quicksort and the leftmost flag 431 * @param parallel indicates whether sorting is performed in parallel 432 * @param low the index of the first element, inclusive, to be sorted 433 * @param high the index of the last element, exclusive, to be sorted 434 */ 435 private static void sort(long[] a, int bits, boolean parallel, int low, int high) { 436 int end = high - 1, length = high - low; 437 438 /* 439 * Run insertion sorts on non-leftmost part. 440 */ 441 if ((bits & 1) > 0) { 442 443 /* 444 * Use nano insertion sort on tiny part. 445 */ 446 if (length < NANO_INSERTION_SORT_THRESHOLD) { 447 SortingAlgorithms.nanoInsertionSort(a, low, high); 448 return; 449 } 450 451 /* 452 * Use pair insertion sort on small part. 453 */ 454 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 455 SortingAlgorithms.pairInsertionSort(a, low, end); 456 return; 457 } 458 } 459 460 /* 461 * Switch to heap sort on the leftmost part or 462 * if the execution time is becoming quadratic. 463 */ 464 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 465 SortingAlgorithms.heapSort(a, low, end); 466 return; 467 } 468 469 /* 470 * Check if the array is nearly sorted 471 * and then try to sort it by Merging sort. 472 */ 473 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 474 return; 475 } 476 477 /* 478 * The splitting of the array, defined by the following 479 * step, is related to the inexpensive approximation of 480 * the golden ratio. 481 */ 482 int step = (length >> 3) * 3 + 3; 483 484 /* 485 * Five elements around (and including) the central element in 486 * the array will be used for pivot selection as described below. 487 * The unequal choice of spacing these elements was empirically 488 * determined to work well on a wide variety of inputs. 489 */ 490 int e1 = low + step; 491 int e5 = end - step; 492 int e3 = (e1 + e5) >>> 1; 493 int e2 = (e1 + e3) >>> 1; 494 int e4 = (e3 + e5) >>> 1; 495 496 /* 497 * Sort these elements in place by the combination 498 * of 5-element sorting network and insertion sort. 499 */ 500 if (a[e5] < a[e3]) { long t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 501 if (a[e4] < a[e2]) { long t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 502 if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 503 if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 504 if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 505 506 if (a[e1] > a[e2]) { long t = a[e1]; a[e1] = a[e2]; a[e2] = t; 507 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 508 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 509 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 510 } 511 } 512 } 513 514 // Pointers 515 int lower = low; // The index of the last element of the left part 516 int upper = end; // The index of the first element of the right part 517 518 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 519 520 /* 521 * Use the first and the fifth elements as the pivots. 522 * These values are inexpensive approximation of tertiles. 523 * Note, that pivot1 < pivot2. 524 */ 525 long pivot1 = a[e1]; 526 long pivot2 = a[e5]; 527 528 /* 529 * The first and the last elements to be sorted are moved to the 530 * locations formerly occupied by the pivots. When partitioning 531 * is completed, the pivots are swapped back into their final 532 * positions, and excluded from subsequent sorting. 533 */ 534 a[e1] = a[lower]; 535 a[e5] = a[upper]; 536 537 /* 538 * Skip elements, which are less or greater than the pivots. 539 */ 540 while (a[++lower] < pivot1); 541 while (a[--upper] > pivot2); 542 543 /* 544 * Backwards 3-interval partitioning 545 * 546 * left part central part right part 547 * +------------------------------------------------------------+ 548 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 549 * +------------------------------------------------------------+ 550 * ^ ^ ^ 551 * | | | 552 * lower k upper 553 * 554 * Invariants: 555 * 556 * all in (low, lower] < pivot1 557 * pivot1 <= all in (k, upper) <= pivot2 558 * all in [upper, end) > pivot2 559 * 560 * Pointer k is the last index of ?-part 561 */ 562 for (int $ = --lower, k = ++upper; --k > lower; ) { 563 long ak = a[k]; 564 565 if (ak < pivot1) { // Move a[k] to the left side 566 while (a[++lower] < pivot1); 567 568 if (lower > k) { 569 lower = k; 570 break; 571 } 572 if (a[lower] > pivot2) { // a[lower] >= pivot1 573 a[k] = a[--upper]; 574 a[upper] = a[lower]; 575 } else { // pivot1 <= a[lower] <= pivot2 576 a[k] = a[lower]; 577 } 578 a[lower] = ak; 579 } else if (ak > pivot2) { // Move a[k] to the right side 580 a[k] = a[--upper]; 581 a[upper] = ak; 582 } 583 } 584 585 /* 586 * Swap the pivots into their final positions. 587 */ 588 a[low] = a[lower]; a[lower] = pivot1; 589 a[end] = a[upper]; a[upper] = pivot2; 590 591 /* 592 * Sort all parts recursively, excluding known pivots. 593 */ 594 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 595 ForkJoinTask.invokeAll( 596 new Sorter<long[]>(a, bits | 1, lower + 1, upper), 597 new Sorter<long[]>(a, bits | 1, upper + 1, high), 598 new Sorter<long[]>(a, bits, low, lower) 599 ); 600 } else { 601 sort(a, bits | 1, false, upper + 1, high); 602 sort(a, bits, false, low, lower); 603 sort(a, bits | 1, false, lower + 1, upper); 604 } 605 } else { // Partitioning with one pivot 606 607 /* 608 * Use the third element as the pivot. This value 609 * is inexpensive approximation of the median. 610 */ 611 long pivot = a[e3]; 612 613 /* 614 * The first element to be sorted is moved to the location 615 * formerly occupied by the pivot. When partitioning is 616 * completed, the pivot is swapped back into its final 617 * position, and excluded from subsequent sorting. 618 */ 619 a[e3] = a[lower]; 620 621 /* 622 * Traditional 3-way (Dutch National Flag) partitioning 623 * 624 * left part central part right part 625 * +------------------------------------------------------+ 626 * | < pivot | ? | == pivot | > pivot | 627 * +------------------------------------------------------+ 628 * ^ ^ ^ 629 * | | | 630 * lower k upper 631 * 632 * Invariants: 633 * 634 * all in (low, lower] < pivot 635 * all in (k, upper) == pivot 636 * all in [upper, end] > pivot 637 * 638 * Pointer k is the last index of ?-part 639 */ 640 for (int k = ++upper; --k > lower; ) { 641 if (a[k] == pivot) { 642 continue; 643 } 644 long ak = a[k]; 645 646 if (ak < pivot) { // Move a[k] to the left side 647 while (a[++lower] < pivot); 648 649 if (lower > k) { 650 lower = k; 651 break; 652 } 653 a[k] = pivot; 654 655 if (a[lower] > pivot) { 656 a[--upper] = a[lower]; 657 } 658 a[lower] = ak; 659 } else { // ak > pivot - Move a[k] to the right side 660 a[k] = pivot; 661 a[--upper] = ak; 662 } 663 } 664 665 /* 666 * Swap the pivot into its final position. 667 */ 668 a[low] = a[lower]; a[lower] = pivot; 669 670 /* 671 * Sort the left and the right parts recursively, excluding 672 * known pivot. All elements from the central part are equal 673 * and, therefore, already sorted. 674 */ 675 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 676 ForkJoinTask.invokeAll( 677 new Sorter<long[]>(a, bits, low, lower), 678 new Sorter<long[]>(a, bits | 1, upper, high) 679 ); 680 } else { 681 sort(a, bits | 1, false, upper, high); 682 sort(a, bits, false, low, lower); 683 } 684 } 685 } 686 687 /** 688 * Sorts the specified range of the array. 689 * 690 * @param a the array to be sorted 691 * @param parallel indicates whether sorting is performed in parallel 692 * @param low the index of the first element, inclusive, to be sorted 693 * @param high the index of the last element, exclusive, to be sorted 694 */ 695 static void sort(byte[] a, boolean parallel, int low, int high) { 696 if (high - low > COUNTING_SORT_THRESHOLD_FOR_BYTE) { 697 SortingAlgorithms.countingSort(a, low, high); 698 } else { 699 SortingAlgorithms.insertionSort(a, low, high); 700 } 701 } 702 703 /** 704 * Sorts the specified range of the array. 705 * 706 * @param a the array to be sorted 707 * @param parallel indicates whether sorting is performed in parallel 708 * @param low the index of the first element, inclusive, to be sorted 709 * @param high the index of the last element, exclusive, to be sorted 710 */ 711 static void sort(char[] a, boolean parallel, int low, int high) { 712 if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { 713 SortingAlgorithms.countingSort(a, low, high); 714 } else { 715 sort(a, LEFTMOST_BITS, parallel, low, high); 716 } 717 } 718 719 /** 720 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 721 * 722 * @param a the array to be sorted 723 * @param bits the recursion depth of Quicksort and the leftmost flag 724 * @param parallel indicates whether sorting is performed in parallel 725 * @param low the index of the first element, inclusive, to be sorted 726 * @param high the index of the last element, exclusive, to be sorted 727 */ 728 private static void sort(char[] a, int bits, boolean parallel, int low, int high) { 729 int end = high - 1, length = high - low; 730 731 /* 732 * Run insertion sorts on non-leftmost part. 733 */ 734 if ((bits & 1) > 0) { 735 736 /* 737 * Use nano insertion sort on tiny part. 738 */ 739 if (length < NANO_INSERTION_SORT_THRESHOLD) { 740 SortingAlgorithms.nanoInsertionSort(a, low, high); 741 return; 742 } 743 744 /* 745 * Use pair insertion sort on small part. 746 */ 747 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 748 SortingAlgorithms.pairInsertionSort(a, low, end); 749 return; 750 } 751 } 752 753 /* 754 * Switch to heap sort on the leftmost part or 755 * if the execution time is becoming quadratic. 756 */ 757 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 758 SortingAlgorithms.heapSort(a, low, end); 759 return; 760 } 761 762 /* 763 * Check if the array is nearly sorted 764 * and then try to sort it by Merging sort. 765 */ 766 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 767 return; 768 } 769 770 /* 771 * The splitting of the array, defined by the following 772 * step, is related to the inexpensive approximation of 773 * the golden ratio. 774 */ 775 int step = (length >> 3) * 3 + 3; 776 777 /* 778 * Five elements around (and including) the central element in 779 * the array will be used for pivot selection as described below. 780 * The unequal choice of spacing these elements was empirically 781 * determined to work well on a wide variety of inputs. 782 */ 783 int e1 = low + step; 784 int e5 = end - step; 785 int e3 = (e1 + e5) >>> 1; 786 int e2 = (e1 + e3) >>> 1; 787 int e4 = (e3 + e5) >>> 1; 788 789 /* 790 * Sort these elements in place by the combination 791 * of 5-element sorting network and insertion sort. 792 */ 793 if (a[e5] < a[e3]) { char t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 794 if (a[e4] < a[e2]) { char t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 795 if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 796 if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 797 if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 798 799 if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; 800 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 801 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 802 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 803 } 804 } 805 } 806 807 // Pointers 808 int lower = low; // The index of the last element of the left part 809 int upper = end; // The index of the first element of the right part 810 811 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 812 813 /* 814 * Use the first and the fifth elements as the pivots. 815 * These values are inexpensive approximation of tertiles. 816 * Note, that pivot1 < pivot2. 817 */ 818 char pivot1 = a[e1]; 819 char pivot2 = a[e5]; 820 821 /* 822 * The first and the last elements to be sorted are moved to the 823 * locations formerly occupied by the pivots. When partitioning 824 * is completed, the pivots are swapped back into their final 825 * positions, and excluded from subsequent sorting. 826 */ 827 a[e1] = a[lower]; 828 a[e5] = a[upper]; 829 830 /* 831 * Skip elements, which are less or greater than the pivots. 832 */ 833 while (a[++lower] < pivot1); 834 while (a[--upper] > pivot2); 835 836 /* 837 * Backwards 3-interval partitioning 838 * 839 * left part central part right part 840 * +------------------------------------------------------------+ 841 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 842 * +------------------------------------------------------------+ 843 * ^ ^ ^ 844 * | | | 845 * lower k upper 846 * 847 * Invariants: 848 * 849 * all in (low, lower] < pivot1 850 * pivot1 <= all in (k, upper) <= pivot2 851 * all in [upper, end) > pivot2 852 * 853 * Pointer k is the last index of ?-part 854 */ 855 for (int $ = --lower, k = ++upper; --k > lower; ) { 856 char ak = a[k]; 857 858 if (ak < pivot1) { // Move a[k] to the left side 859 while (a[++lower] < pivot1); 860 861 if (lower > k) { 862 lower = k; 863 break; 864 } 865 if (a[lower] > pivot2) { // a[lower] >= pivot1 866 a[k] = a[--upper]; 867 a[upper] = a[lower]; 868 } else { // pivot1 <= a[lower] <= pivot2 869 a[k] = a[lower]; 870 } 871 a[lower] = ak; 872 } else if (ak > pivot2) { // Move a[k] to the right side 873 a[k] = a[--upper]; 874 a[upper] = ak; 875 } 876 } 877 878 /* 879 * Swap the pivots into their final positions. 880 */ 881 a[low] = a[lower]; a[lower] = pivot1; 882 a[end] = a[upper]; a[upper] = pivot2; 883 884 /* 885 * Sort all parts recursively, excluding known pivots. 886 */ 887 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 888 ForkJoinTask.invokeAll( 889 new Sorter<char[]>(a, bits | 1, lower + 1, upper), 890 new Sorter<char[]>(a, bits | 1, upper + 1, high), 891 new Sorter<char[]>(a, bits, low, lower) 892 ); 893 } else { 894 sort(a, bits | 1, false, upper + 1, high); 895 sort(a, bits, false, low, lower); 896 sort(a, bits | 1, false, lower + 1, upper); 897 } 898 } else { // Partitioning with one pivot 899 900 /* 901 * Use the third element as the pivot. This value 902 * is inexpensive approximation of the median. 903 */ 904 char pivot = a[e3]; 905 906 /* 907 * The first element to be sorted is moved to the location 908 * formerly occupied by the pivot. When partitioning is 909 * completed, the pivot is swapped back into its final 910 * position, and excluded from subsequent sorting. 911 */ 912 a[e3] = a[lower]; 913 914 /* 915 * Traditional 3-way (Dutch National Flag) partitioning 916 * 917 * left part central part right part 918 * +------------------------------------------------------+ 919 * | < pivot | ? | == pivot | > pivot | 920 * +------------------------------------------------------+ 921 * ^ ^ ^ 922 * | | | 923 * lower k upper 924 * 925 * Invariants: 926 * 927 * all in (low, lower] < pivot 928 * all in (k, upper) == pivot 929 * all in [upper, end] > pivot 930 * 931 * Pointer k is the last index of ?-part 932 */ 933 for (int k = ++upper; --k > lower; ) { 934 if (a[k] == pivot) { 935 continue; 936 } 937 char ak = a[k]; 938 939 if (ak < pivot) { // Move a[k] to the left side 940 while (a[++lower] < pivot); 941 942 if (lower > k) { 943 lower = k; 944 break; 945 } 946 a[k] = pivot; 947 948 if (a[lower] > pivot) { 949 a[--upper] = a[lower]; 950 } 951 a[lower] = ak; 952 } else { // ak > pivot - Move a[k] to the right side 953 a[k] = pivot; 954 a[--upper] = ak; 955 } 956 } 957 958 /* 959 * Swap the pivot into its final position. 960 */ 961 a[low] = a[lower]; a[lower] = pivot; 962 963 /* 964 * Sort the left and the right parts recursively, excluding 965 * known pivot. All elements from the central part are equal 966 * and, therefore, already sorted. 967 */ 968 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 969 ForkJoinTask.invokeAll( 970 new Sorter<char[]>(a, bits, low, lower), 971 new Sorter<char[]>(a, bits | 1, upper, high) 972 ); 973 } else { 974 sort(a, bits | 1, false, upper, high); 975 sort(a, bits, false, low, lower); 976 } 977 } 978 } 979 980 /** 981 * Sorts the specified range of the array. 982 * 983 * @param a the array to be sorted 984 * @param parallel indicates whether sorting is performed in parallel 985 * @param low the index of the first element, inclusive, to be sorted 986 * @param high the index of the last element, exclusive, to be sorted 987 */ 988 static void sort(short[] a, boolean parallel, int low, int high) { 989 if (high - low > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { 990 SortingAlgorithms.countingSort(a, low, high); 991 } else { 992 sort(a, LEFTMOST_BITS, parallel, low, high); 993 } 994 } 995 996 /** 997 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 998 * 999 * @param a the array to be sorted 1000 * @param bits the recursion depth of Quicksort and the leftmost flag 1001 * @param parallel indicates whether sorting is performed in parallel 1002 * @param low the index of the first element, inclusive, to be sorted 1003 * @param high the index of the last element, exclusive, to be sorted 1004 */ 1005 private static void sort(short[] a, int bits, boolean parallel, int low, int high) { 1006 int end = high - 1, length = high - low; 1007 1008 /* 1009 * Run insertion sorts on non-leftmost part. 1010 */ 1011 if ((bits & 1) > 0) { 1012 1013 /* 1014 * Use nano insertion sort on tiny part. 1015 */ 1016 if (length < NANO_INSERTION_SORT_THRESHOLD) { 1017 SortingAlgorithms.nanoInsertionSort(a, low, high); 1018 return; 1019 } 1020 1021 /* 1022 * Use pair insertion sort on small part. 1023 */ 1024 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 1025 SortingAlgorithms.pairInsertionSort(a, low, end); 1026 return; 1027 } 1028 } 1029 1030 /* 1031 * Switch to heap sort on the leftmost part or 1032 * if the execution time is becoming quadratic. 1033 */ 1034 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 1035 SortingAlgorithms.heapSort(a, low, end); 1036 return; 1037 } 1038 1039 /* 1040 * Check if the array is nearly sorted 1041 * and then try to sort it by Merging sort. 1042 */ 1043 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 1044 return; 1045 } 1046 1047 /* 1048 * The splitting of the array, defined by the following 1049 * step, is related to the inexpensive approximation of 1050 * the golden ratio. 1051 */ 1052 int step = (length >> 3) * 3 + 3; 1053 1054 /* 1055 * Five elements around (and including) the central element in 1056 * the array will be used for pivot selection as described below. 1057 * The unequal choice of spacing these elements was empirically 1058 * determined to work well on a wide variety of inputs. 1059 */ 1060 int e1 = low + step; 1061 int e5 = end - step; 1062 int e3 = (e1 + e5) >>> 1; 1063 int e2 = (e1 + e3) >>> 1; 1064 int e4 = (e3 + e5) >>> 1; 1065 1066 /* 1067 * Sort these elements in place by the combination 1068 * of 5-element sorting network and insertion sort. 1069 */ 1070 if (a[e5] < a[e3]) { short t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 1071 if (a[e4] < a[e2]) { short t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 1072 if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 1073 if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 1074 if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 1075 1076 if (a[e1] > a[e2]) { short t = a[e1]; a[e1] = a[e2]; a[e2] = t; 1077 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 1078 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 1079 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 1080 } 1081 } 1082 } 1083 1084 // Pointers 1085 int lower = low; // The index of the last element of the left part 1086 int upper = end; // The index of the first element of the right part 1087 1088 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 1089 1090 /* 1091 * Use the first and the fifth elements as the pivots. 1092 * These values are inexpensive approximation of tertiles. 1093 * Note, that pivot1 < pivot2. 1094 */ 1095 short pivot1 = a[e1]; 1096 short pivot2 = a[e5]; 1097 1098 /* 1099 * The first and the last elements to be sorted are moved to the 1100 * locations formerly occupied by the pivots. When partitioning 1101 * is completed, the pivots are swapped back into their final 1102 * positions, and excluded from subsequent sorting. 1103 */ 1104 a[e1] = a[lower]; 1105 a[e5] = a[upper]; 1106 1107 /* 1108 * Skip elements, which are less or greater than the pivots. 1109 */ 1110 while (a[++lower] < pivot1); 1111 while (a[--upper] > pivot2); 1112 1113 /* 1114 * Backwards 3-interval partitioning 1115 * 1116 * left part central part right part 1117 * +------------------------------------------------------------+ 1118 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 1119 * +------------------------------------------------------------+ 1120 * ^ ^ ^ 1121 * | | | 1122 * lower k upper 1123 * 1124 * Invariants: 1125 * 1126 * all in (low, lower] < pivot1 1127 * pivot1 <= all in (k, upper) <= pivot2 1128 * all in [upper, end) > pivot2 1129 * 1130 * Pointer k is the last index of ?-part 1131 */ 1132 for (int $ = --lower, k = ++upper; --k > lower; ) { 1133 short ak = a[k]; 1134 1135 if (ak < pivot1) { // Move a[k] to the left side 1136 while (a[++lower] < pivot1); 1137 1138 if (lower > k) { 1139 lower = k; 1140 break; 1141 } 1142 if (a[lower] > pivot2) { // a[lower] >= pivot1 1143 a[k] = a[--upper]; 1144 a[upper] = a[lower]; 1145 } else { // pivot1 <= a[lower] <= pivot2 1146 a[k] = a[lower]; 1147 } 1148 a[lower] = ak; 1149 } else if (ak > pivot2) { // Move a[k] to the right side 1150 a[k] = a[--upper]; 1151 a[upper] = ak; 1152 } 1153 } 1154 1155 /* 1156 * Swap the pivots into their final positions. 1157 */ 1158 a[low] = a[lower]; a[lower] = pivot1; 1159 a[end] = a[upper]; a[upper] = pivot2; 1160 1161 /* 1162 * Sort all parts recursively, excluding known pivots. 1163 */ 1164 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1165 ForkJoinTask.invokeAll( 1166 new Sorter<short[]>(a, bits | 1, lower + 1, upper), 1167 new Sorter<short[]>(a, bits | 1, upper + 1, high), 1168 new Sorter<short[]>(a, bits, low, lower) 1169 ); 1170 } else { 1171 sort(a, bits | 1, false, upper + 1, high); 1172 sort(a, bits, false, low, lower); 1173 sort(a, bits | 1, false, lower + 1, upper); 1174 } 1175 } else { // Partitioning with one pivot 1176 1177 /* 1178 * Use the third element as the pivot. This value 1179 * is inexpensive approximation of the median. 1180 */ 1181 short pivot = a[e3]; 1182 1183 /* 1184 * The first element to be sorted is moved to the location 1185 * formerly occupied by the pivot. When partitioning is 1186 * completed, the pivot is swapped back into its final 1187 * position, and excluded from subsequent sorting. 1188 */ 1189 a[e3] = a[lower]; 1190 1191 /* 1192 * Traditional 3-way (Dutch National Flag) partitioning 1193 * 1194 * left part central part right part 1195 * +------------------------------------------------------+ 1196 * | < pivot | ? | == pivot | > pivot | 1197 * +------------------------------------------------------+ 1198 * ^ ^ ^ 1199 * | | | 1200 * lower k upper 1201 * 1202 * Invariants: 1203 * 1204 * all in (low, lower] < pivot 1205 * all in (k, upper) == pivot 1206 * all in [upper, end] > pivot 1207 * 1208 * Pointer k is the last index of ?-part 1209 */ 1210 for (int k = ++upper; --k > lower; ) { 1211 if (a[k] == pivot) { 1212 continue; 1213 } 1214 short ak = a[k]; 1215 1216 if (ak < pivot) { // Move a[k] to the left side 1217 while (a[++lower] < pivot); 1218 1219 if (lower > k) { 1220 lower = k; 1221 break; 1222 } 1223 a[k] = pivot; 1224 1225 if (a[lower] > pivot) { 1226 a[--upper] = a[lower]; 1227 } 1228 a[lower] = ak; 1229 } else { // ak > pivot - Move a[k] to the right side 1230 a[k] = pivot; 1231 a[--upper] = ak; 1232 } 1233 } 1234 1235 /* 1236 * Swap the pivot into its final position. 1237 */ 1238 a[low] = a[lower]; a[lower] = pivot; 1239 1240 /* 1241 * Sort the left and the right parts recursively, excluding 1242 * known pivot. All elements from the central part are equal 1243 * and, therefore, already sorted. 1244 */ 1245 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1246 ForkJoinTask.invokeAll( 1247 new Sorter<short[]>(a, bits, low, lower), 1248 new Sorter<short[]>(a, bits | 1, upper, high) 1249 ); 1250 } else { 1251 sort(a, bits | 1, false, upper, high); 1252 sort(a, bits, false, low, lower); 1253 } 1254 } 1255 } 1256 1257 /** 1258 * Sorts the specified range of the array. 1259 * 1260 * @param a the array to be sorted 1261 * @param parallel indicates whether sorting is performed in parallel 1262 * @param low the index of the first element, inclusive, to be sorted 1263 * @param high the index of the last element, exclusive, to be sorted 1264 */ 1265 static void sort(float[] a, boolean parallel, int low, int high) { 1266 /* 1267 * Phase 1. Count the number of negative zero -0.0f, 1268 * turn them into positive zero, and move all NaNs 1269 * to the end of the array. 1270 */ 1271 int numNegativeZero = 0; 1272 1273 for (int k = high; k > low; ) { 1274 float ak = a[--k]; 1275 1276 if (ak == 0.0f && Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f 1277 numNegativeZero += 1; 1278 a[k] = 0.0f; 1279 } else if (ak != ak) { // ak is NaN 1280 a[k] = a[--high]; 1281 a[high] = ak; 1282 } 1283 } 1284 1285 /* 1286 * Phase 2. Sort everything except NaNs, 1287 * which are already in place. 1288 */ 1289 sort(a, LEFTMOST_BITS, parallel, low, high); 1290 1291 /* 1292 * Phase 3. Turn positive zero 0.0f 1293 * back into negative zero -0.0f. 1294 */ 1295 if (++numNegativeZero == 1) { 1296 return; 1297 } 1298 1299 /* 1300 * Find the position one less than 1301 * the index of the first zero. 1302 */ 1303 while (low <= high) { 1304 int middle = (low + high) >>> 1; 1305 1306 if (a[middle] < 0) { 1307 low = middle + 1; 1308 } else { 1309 high = middle - 1; 1310 } 1311 } 1312 1313 /* 1314 * Replace the required number of 0.0f by -0.0f. 1315 */ 1316 while (--numNegativeZero > 0) { 1317 a[++high] = -0.0f; 1318 } 1319 } 1320 1321 /** 1322 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 1323 * 1324 * @param a the array to be sorted 1325 * @param bits the recursion depth of Quicksort and the leftmost flag 1326 * @param parallel indicates whether sorting is performed in parallel 1327 * @param low the index of the first element, inclusive, to be sorted 1328 * @param high the index of the last element, exclusive, to be sorted 1329 */ 1330 private static void sort(float[] a, int bits, boolean parallel, int low, int high) { 1331 int end = high - 1, length = high - low; 1332 1333 /* 1334 * Run insertion sorts on non-leftmost part. 1335 */ 1336 if ((bits & 1) > 0) { 1337 1338 /* 1339 * Use nano insertion sort on tiny part. 1340 */ 1341 if (length < NANO_INSERTION_SORT_THRESHOLD) { 1342 SortingAlgorithms.nanoInsertionSort(a, low, high); 1343 return; 1344 } 1345 1346 /* 1347 * Use pair insertion sort on small part. 1348 */ 1349 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 1350 SortingAlgorithms.pairInsertionSort(a, low, end); 1351 return; 1352 } 1353 } 1354 1355 /* 1356 * Switch to heap sort on the leftmost part or 1357 * if the execution time is becoming quadratic. 1358 */ 1359 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 1360 SortingAlgorithms.heapSort(a, low, end); 1361 return; 1362 } 1363 1364 /* 1365 * Check if the array is nearly sorted 1366 * and then try to sort it by Merging sort. 1367 */ 1368 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 1369 return; 1370 } 1371 1372 /* 1373 * The splitting of the array, defined by the following 1374 * step, is related to the inexpensive approximation of 1375 * the golden ratio. 1376 */ 1377 int step = (length >> 3) * 3 + 3; 1378 1379 /* 1380 * Five elements around (and including) the central element in 1381 * the array will be used for pivot selection as described below. 1382 * The unequal choice of spacing these elements was empirically 1383 * determined to work well on a wide variety of inputs. 1384 */ 1385 int e1 = low + step; 1386 int e5 = end - step; 1387 int e3 = (e1 + e5) >>> 1; 1388 int e2 = (e1 + e3) >>> 1; 1389 int e4 = (e3 + e5) >>> 1; 1390 1391 /* 1392 * Sort these elements in place by the combination 1393 * of 5-element sorting network and insertion sort. 1394 */ 1395 if (a[e5] < a[e3]) { float t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 1396 if (a[e4] < a[e2]) { float t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 1397 if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 1398 if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 1399 if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 1400 1401 if (a[e1] > a[e2]) { float t = a[e1]; a[e1] = a[e2]; a[e2] = t; 1402 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 1403 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 1404 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 1405 } 1406 } 1407 } 1408 1409 // Pointers 1410 int lower = low; // The index of the last element of the left part 1411 int upper = end; // The index of the first element of the right part 1412 1413 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 1414 1415 /* 1416 * Use the first and the fifth elements as the pivots. 1417 * These values are inexpensive approximation of tertiles. 1418 * Note, that pivot1 < pivot2. 1419 */ 1420 float pivot1 = a[e1]; 1421 float pivot2 = a[e5]; 1422 1423 /* 1424 * The first and the last elements to be sorted are moved to the 1425 * locations formerly occupied by the pivots. When partitioning 1426 * is completed, the pivots are swapped back into their final 1427 * positions, and excluded from subsequent sorting. 1428 */ 1429 a[e1] = a[lower]; 1430 a[e5] = a[upper]; 1431 1432 /* 1433 * Skip elements, which are less or greater than the pivots. 1434 */ 1435 while (a[++lower] < pivot1); 1436 while (a[--upper] > pivot2); 1437 1438 /* 1439 * Backwards 3-interval partitioning 1440 * 1441 * left part central part right part 1442 * +------------------------------------------------------------+ 1443 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 1444 * +------------------------------------------------------------+ 1445 * ^ ^ ^ 1446 * | | | 1447 * lower k upper 1448 * 1449 * Invariants: 1450 * 1451 * all in (low, lower] < pivot1 1452 * pivot1 <= all in (k, upper) <= pivot2 1453 * all in [upper, end) > pivot2 1454 * 1455 * Pointer k is the last index of ?-part 1456 */ 1457 for (int $ = --lower, k = ++upper; --k > lower; ) { 1458 float ak = a[k]; 1459 1460 if (ak < pivot1) { // Move a[k] to the left side 1461 while (a[++lower] < pivot1); 1462 1463 if (lower > k) { 1464 lower = k; 1465 break; 1466 } 1467 if (a[lower] > pivot2) { // a[lower] >= pivot1 1468 a[k] = a[--upper]; 1469 a[upper] = a[lower]; 1470 } else { // pivot1 <= a[lower] <= pivot2 1471 a[k] = a[lower]; 1472 } 1473 a[lower] = ak; 1474 } else if (ak > pivot2) { // Move a[k] to the right side 1475 a[k] = a[--upper]; 1476 a[upper] = ak; 1477 } 1478 } 1479 1480 /* 1481 * Swap the pivots into their final positions. 1482 */ 1483 a[low] = a[lower]; a[lower] = pivot1; 1484 a[end] = a[upper]; a[upper] = pivot2; 1485 1486 /* 1487 * Sort all parts recursively, excluding known pivots. 1488 */ 1489 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1490 ForkJoinTask.invokeAll( 1491 new Sorter<float[]>(a, bits | 1, lower + 1, upper), 1492 new Sorter<float[]>(a, bits | 1, upper + 1, high), 1493 new Sorter<float[]>(a, bits, low, lower) 1494 ); 1495 } else { 1496 sort(a, bits | 1, false, upper + 1, high); 1497 sort(a, bits, false, low, lower); 1498 sort(a, bits | 1, false, lower + 1, upper); 1499 } 1500 } else { // Partitioning with one pivot 1501 1502 /* 1503 * Use the third element as the pivot. This value 1504 * is inexpensive approximation of the median. 1505 */ 1506 float pivot = a[e3]; 1507 1508 /* 1509 * The first element to be sorted is moved to the location 1510 * formerly occupied by the pivot. When partitioning is 1511 * completed, the pivot is swapped back into its final 1512 * position, and excluded from subsequent sorting. 1513 */ 1514 a[e3] = a[lower]; 1515 1516 /* 1517 * Traditional 3-way (Dutch National Flag) partitioning 1518 * 1519 * left part central part right part 1520 * +------------------------------------------------------+ 1521 * | < pivot | ? | == pivot | > pivot | 1522 * +------------------------------------------------------+ 1523 * ^ ^ ^ 1524 * | | | 1525 * lower k upper 1526 * 1527 * Invariants: 1528 * 1529 * all in (low, lower] < pivot 1530 * all in (k, upper) == pivot 1531 * all in [upper, end] > pivot 1532 * 1533 * Pointer k is the last index of ?-part 1534 */ 1535 for (int k = ++upper; --k > lower; ) { 1536 if (a[k] == pivot) { 1537 continue; 1538 } 1539 float ak = a[k]; 1540 1541 if (ak < pivot) { // Move a[k] to the left side 1542 while (a[++lower] < pivot); 1543 1544 if (lower > k) { 1545 lower = k; 1546 break; 1547 } 1548 a[k] = pivot; 1549 1550 if (a[lower] > pivot) { 1551 a[--upper] = a[lower]; 1552 } 1553 a[lower] = ak; 1554 } else { // ak > pivot - Move a[k] to the right side 1555 a[k] = pivot; 1556 a[--upper] = ak; 1557 } 1558 } 1559 1560 /* 1561 * Swap the pivot into its final position. 1562 */ 1563 a[low] = a[lower]; a[lower] = pivot; 1564 1565 /* 1566 * Sort the left and the right parts recursively, excluding 1567 * known pivot. All elements from the central part are equal 1568 * and, therefore, already sorted. 1569 */ 1570 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1571 ForkJoinTask.invokeAll( 1572 new Sorter<float[]>(a, bits, low, lower), 1573 new Sorter<float[]>(a, bits | 1, upper, high) 1574 ); 1575 } else { 1576 sort(a, bits | 1, false, upper, high); 1577 sort(a, bits, false, low, lower); 1578 } 1579 } 1580 } 1581 1582 /** 1583 * Sorts the specified range of the array. 1584 * 1585 * @param a the array to be sorted 1586 * @param parallel indicates whether sorting is performed in parallel 1587 * @param low the index of the first element, inclusive, to be sorted 1588 * @param high the index of the last element, exclusive, to be sorted 1589 */ 1590 static void sort(double[] a, boolean parallel, int low, int high) { 1591 /* 1592 * Phase 1. Count the number of negative zero -0.0d, 1593 * turn them into positive zero, and move all NaNs 1594 * to the end of the array. 1595 */ 1596 int numNegativeZero = 0; 1597 1598 for (int k = high; k > low; ) { 1599 double ak = a[--k]; 1600 1601 if (ak == 0.0d && Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d 1602 numNegativeZero += 1; 1603 a[k] = 0.0d; 1604 } else if (ak != ak) { // ak is NaN 1605 a[k] = a[--high]; 1606 a[high] = ak; 1607 } 1608 } 1609 1610 /* 1611 * Phase 2. Sort everything except NaNs, 1612 * which are already in place. 1613 */ 1614 sort(a, LEFTMOST_BITS, parallel, low, high); 1615 1616 /* 1617 * Phase 3. Turn positive zero 0.0d 1618 * back into negative zero -0.0d. 1619 */ 1620 if (++numNegativeZero == 1) { 1621 return; 1622 } 1623 1624 /* 1625 * Find the position one less than 1626 * the index of the first zero. 1627 */ 1628 while (low <= high) { 1629 int middle = (low + high) >>> 1; 1630 1631 if (a[middle] < 0) { 1632 low = middle + 1; 1633 } else { 1634 high = middle - 1; 1635 } 1636 } 1637 1638 /* 1639 * Replace the required number of 0.0d by -0.0d. 1640 */ 1641 while (--numNegativeZero > 0) { 1642 a[++high] = -0.0d; 1643 } 1644 } 1645 1646 /** 1647 * Sorts the specified range of the array by the Dual-Pivot Quicksort. 1648 * 1649 * @param a the array to be sorted 1650 * @param bits the recursion depth of Quicksort and the leftmost flag 1651 * @param parallel indicates whether sorting is performed in parallel 1652 * @param low the index of the first element, inclusive, to be sorted 1653 * @param high the index of the last element, exclusive, to be sorted 1654 */ 1655 private static void sort(double[] a, int bits, boolean parallel, int low, int high) { 1656 int end = high - 1, length = high - low; 1657 1658 /* 1659 * Run insertion sorts on non-leftmost part. 1660 */ 1661 if ((bits & 1) > 0) { 1662 1663 /* 1664 * Use nano insertion sort on tiny part. 1665 */ 1666 if (length < NANO_INSERTION_SORT_THRESHOLD) { 1667 SortingAlgorithms.nanoInsertionSort(a, low, high); 1668 return; 1669 } 1670 1671 /* 1672 * Use pair insertion sort on small part. 1673 */ 1674 if (length < PAIR_INSERTION_SORT_THRESHOLD) { 1675 SortingAlgorithms.pairInsertionSort(a, low, end); 1676 return; 1677 } 1678 } 1679 1680 /* 1681 * Switch to heap sort on the leftmost part or 1682 * if the execution time is becoming quadratic. 1683 */ 1684 if (length < HEAP_SORT_THRESHOLD || (bits -= 2) < 0) { 1685 SortingAlgorithms.heapSort(a, low, end); 1686 return; 1687 } 1688 1689 /* 1690 * Check if the array is nearly sorted 1691 * and then try to sort it by Merging sort. 1692 */ 1693 if (SortingAlgorithms.mergingSort(a, parallel, low, high)) { 1694 return; 1695 } 1696 1697 /* 1698 * The splitting of the array, defined by the following 1699 * step, is related to the inexpensive approximation of 1700 * the golden ratio. 1701 */ 1702 int step = (length >> 3) * 3 + 3; 1703 1704 /* 1705 * Five elements around (and including) the central element in 1706 * the array will be used for pivot selection as described below. 1707 * The unequal choice of spacing these elements was empirically 1708 * determined to work well on a wide variety of inputs. 1709 */ 1710 int e1 = low + step; 1711 int e5 = end - step; 1712 int e3 = (e1 + e5) >>> 1; 1713 int e2 = (e1 + e3) >>> 1; 1714 int e4 = (e3 + e5) >>> 1; 1715 1716 /* 1717 * Sort these elements in place by the combination 1718 * of 5-element sorting network and insertion sort. 1719 */ 1720 if (a[e5] < a[e3]) { double t = a[e5]; a[e5] = a[e3]; a[e3] = t; } 1721 if (a[e4] < a[e2]) { double t = a[e4]; a[e4] = a[e2]; a[e2] = t; } 1722 if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t; } 1723 if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t; } 1724 if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t; } 1725 1726 if (a[e1] > a[e2]) { double t = a[e1]; a[e1] = a[e2]; a[e2] = t; 1727 if (t > a[e3]) { a[e2] = a[e3]; a[e3] = t; 1728 if (t > a[e4]) { a[e3] = a[e4]; a[e4] = t; 1729 if (t > a[e5]) { a[e4] = a[e5]; a[e5] = t; } 1730 } 1731 } 1732 } 1733 1734 // Pointers 1735 int lower = low; // The index of the last element of the left part 1736 int upper = end; // The index of the first element of the right part 1737 1738 if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) { 1739 1740 /* 1741 * Use the first and the fifth elements as the pivots. 1742 * These values are inexpensive approximation of tertiles. 1743 * Note, that pivot1 < pivot2. 1744 */ 1745 double pivot1 = a[e1]; 1746 double pivot2 = a[e5]; 1747 1748 /* 1749 * The first and the last elements to be sorted are moved to the 1750 * locations formerly occupied by the pivots. When partitioning 1751 * is completed, the pivots are swapped back into their final 1752 * positions, and excluded from subsequent sorting. 1753 */ 1754 a[e1] = a[lower]; 1755 a[e5] = a[upper]; 1756 1757 /* 1758 * Skip elements, which are less or greater than the pivots. 1759 */ 1760 while (a[++lower] < pivot1); 1761 while (a[--upper] > pivot2); 1762 1763 /* 1764 * Backwards 3-interval partitioning 1765 * 1766 * left part central part right part 1767 * +------------------------------------------------------------+ 1768 * | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 | 1769 * +------------------------------------------------------------+ 1770 * ^ ^ ^ 1771 * | | | 1772 * lower k upper 1773 * 1774 * Invariants: 1775 * 1776 * all in (low, lower] < pivot1 1777 * pivot1 <= all in (k, upper) <= pivot2 1778 * all in [upper, end) > pivot2 1779 * 1780 * Pointer k is the last index of ?-part 1781 */ 1782 for (int $ = --lower, k = ++upper; --k > lower; ) { 1783 double ak = a[k]; 1784 1785 if (ak < pivot1) { // Move a[k] to the left side 1786 while (a[++lower] < pivot1); 1787 1788 if (lower > k) { 1789 lower = k; 1790 break; 1791 } 1792 if (a[lower] > pivot2) { // a[lower] >= pivot1 1793 a[k] = a[--upper]; 1794 a[upper] = a[lower]; 1795 } else { // pivot1 <= a[lower] <= pivot2 1796 a[k] = a[lower]; 1797 } 1798 a[lower] = ak; 1799 } else if (ak > pivot2) { // Move a[k] to the right side 1800 a[k] = a[--upper]; 1801 a[upper] = ak; 1802 } 1803 } 1804 1805 /* 1806 * Swap the pivots into their final positions. 1807 */ 1808 a[low] = a[lower]; a[lower] = pivot1; 1809 a[end] = a[upper]; a[upper] = pivot2; 1810 1811 /* 1812 * Sort all parts recursively, excluding known pivots. 1813 */ 1814 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1815 ForkJoinTask.invokeAll( 1816 new Sorter<double[]>(a, bits | 1, lower + 1, upper), 1817 new Sorter<double[]>(a, bits | 1, upper + 1, high), 1818 new Sorter<double[]>(a, bits, low, lower) 1819 ); 1820 } else { 1821 sort(a, bits | 1, false, upper + 1, high); 1822 sort(a, bits, false, low, lower); 1823 sort(a, bits | 1, false, lower + 1, upper); 1824 } 1825 } else { // Partitioning with one pivot 1826 1827 /* 1828 * Use the third element as the pivot. This value 1829 * is inexpensive approximation of the median. 1830 */ 1831 double pivot = a[e3]; 1832 1833 /* 1834 * The first element to be sorted is moved to the location 1835 * formerly occupied by the pivot. When partitioning is 1836 * completed, the pivot is swapped back into its final 1837 * position, and excluded from subsequent sorting. 1838 */ 1839 a[e3] = a[lower]; 1840 1841 /* 1842 * Traditional 3-way (Dutch National Flag) partitioning 1843 * 1844 * left part central part right part 1845 * +------------------------------------------------------+ 1846 * | < pivot | ? | == pivot | > pivot | 1847 * +------------------------------------------------------+ 1848 * ^ ^ ^ 1849 * | | | 1850 * lower k upper 1851 * 1852 * Invariants: 1853 * 1854 * all in (low, lower] < pivot 1855 * all in (k, upper) == pivot 1856 * all in [upper, end] > pivot 1857 * 1858 * Pointer k is the last index of ?-part 1859 */ 1860 for (int k = ++upper; --k > lower; ) { 1861 if (a[k] == pivot) { 1862 continue; 1863 } 1864 double ak = a[k]; 1865 1866 if (ak < pivot) { // Move a[k] to the left side 1867 while (a[++lower] < pivot); 1868 1869 if (lower > k) { 1870 lower = k; 1871 break; 1872 } 1873 a[k] = pivot; 1874 1875 if (a[lower] > pivot) { 1876 a[--upper] = a[lower]; 1877 } 1878 a[lower] = ak; 1879 } else { // ak > pivot - Move a[k] to the right side 1880 a[k] = pivot; 1881 a[--upper] = ak; 1882 } 1883 } 1884 1885 /* 1886 * Swap the pivot into its final position. 1887 */ 1888 a[low] = a[lower]; a[lower] = pivot; 1889 1890 /* 1891 * Sort the left and the right parts recursively, excluding 1892 * known pivot. All elements from the central part are equal 1893 * and, therefore, already sorted. 1894 */ 1895 if (parallel && length > PARALLEL_QUICKSORT_THRESHOLD) { 1896 ForkJoinTask.invokeAll( 1897 new Sorter<double[]>(a, bits, low, lower), 1898 new Sorter<double[]>(a, bits | 1, upper, high) 1899 ); 1900 } else { 1901 sort(a, bits | 1, false, upper, high); 1902 sort(a, bits, false, low, lower); 1903 } 1904 } 1905 } 1906 }