1 /* 2 * Copyright 2009 Sun Microsystems, Inc. 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. Sun designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 22 * CA 95054 USA or visit www.sun.com if you need additional information or 23 * have any 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 Joshua 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 * @author Vladimir Yaroslavskiy 36 * @author Jon Bentley 37 * @author Josh Bloch 38 * 39 * @version 2009.11.29 m765.827.12i 40 */ 41 final class DualPivotQuicksort { 42 43 /** 44 * Prevents instantiation. 45 */ 46 private DualPivotQuicksort() {} 47 48 /* 49 * Tuning parameters. 50 */ 51 52 /** 53 * If the length of an array to be sorted is less than this 54 * constant, insertion sort is used in preference to Quicksort. 55 */ 56 private static final int INSERTION_SORT_THRESHOLD = 32; 57 58 /** 59 * If the length of a byte array to be sorted is greater than 60 * this constant, counting sort is used in preference to Quicksort. 61 */ 62 private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128; 63 64 /** 65 * If the length of a short or char array to be sorted is greater 66 * than this constant, counting sort is used in preference to Quicksort. 67 */ 68 private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768; 69 70 /* 71 * Sorting methods for 7 primitive types. 72 */ 73 74 /** 75 * Sorts the specified array into ascending numerical order. 76 * 77 * @param a the array to be sorted 78 */ 79 public static void sort(int[] a) { 80 doSort(a, 0, a.length - 1); 81 } 82 83 /** 84 * Sorts the specified range of the array into ascending order. The range 85 * to be sorted extends from the index {@code fromIndex}, inclusive, to 86 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 87 * the range to be sorted is empty (and the call is a no-op). 88 * 89 * @param a the array to be sorted 90 * @param fromIndex the index of the first element, inclusive, to be sorted 91 * @param toIndex the index of the last element, exclusive, to be sorted 92 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 93 * @throws ArrayIndexOutOfBoundsException 94 * if {@code fromIndex < 0} or {@code toIndex > a.length} 95 */ 96 public static void sort(int[] a, int fromIndex, int toIndex) { 97 rangeCheck(a.length, fromIndex, toIndex); 98 doSort(a, fromIndex, toIndex - 1); 99 } 100 101 /** 102 * Sorts the specified range of the array into ascending order. This 103 * method differs from the public {@code sort} method in that the 104 * {@code right} index is inclusive, and it does no range checking 105 * on {@code left} or {@code right}. 106 * 107 * @param a the array to be sorted 108 * @param left the index of the first element, inclusive, to be sorted 109 * @param right the index of the last element, inclusive, to be sorted 110 */ 111 private static void doSort(int[] a, int left, int right) { 112 // Use insertion sort on tiny arrays 113 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 114 for (int i = left + 1; i <= right; i++) { 115 int ai = a[i]; 116 int j; 117 for (j = i - 1; j >= left && ai < a[j]; j--) { 118 a[j + 1] = a[j]; 119 } 120 a[j + 1] = ai; 121 } 122 } else { // Use Dual-Pivot Quicksort on large arrays 123 dualPivotQuicksort(a, left, right); 124 } 125 } 126 127 /** 128 * Sorts the specified range of the array into ascending order by the 129 * Dual-Pivot Quicksort algorithm. 130 * 131 * @param a the array to be sorted 132 * @param left the index of the first element, inclusive, to be sorted 133 * @param right the index of the last element, inclusive, to be sorted 134 */ 135 private static void dualPivotQuicksort(int[] a, int left, int right) { 136 // Compute indices of five evenly spaced elements 137 int sixth = (right - left + 1) / 6; 138 int e1 = left + sixth; 139 int e5 = right - sixth; 140 int e3 = (left + right) >>> 1; // The midpoint 141 int e4 = e3 + sixth; 142 int e2 = e3 - sixth; 143 144 // Sort these elements using a 5-element sorting network 145 int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 146 147 if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; } 148 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; } 149 if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; } 150 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; } 151 if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; } 152 if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; } 153 if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; } 154 if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; } 155 if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; } 156 157 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 158 159 /* 160 * Use the second and fourth of the five sorted elements as pivots. 161 * These values are inexpensive approximations of the first and 162 * second terciles of the array. Note that pivot1 <= pivot2. 163 * 164 * The pivots are stored in local variables, and the first and 165 * the last of the elements to be sorted are moved to the locations 166 * formerly occupied by the pivots. When partitioning is complete, 167 * the pivots are swapped back into their final positions, and 168 * excluded from subsequent sorting. 169 */ 170 int pivot1 = ae2; a[e2] = a[left]; 171 int pivot2 = ae4; a[e4] = a[right]; 172 173 // Pointers 174 int less = left + 1; // The index of first element of center part 175 int great = right - 1; // The index before first element of right part 176 177 boolean pivotsDiffer = (pivot1 != pivot2); 178 179 if (pivotsDiffer) { 180 /* 181 * Partitioning: 182 * 183 * left part center part right part 184 * +------------------------------------------------------------+ 185 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 186 * +------------------------------------------------------------+ 187 * ^ ^ ^ 188 * | | | 189 * less k great 190 * 191 * Invariants: 192 * 193 * all in (left, less) < pivot1 194 * pivot1 <= all in [less, k) <= pivot2 195 * all in (great, right) > pivot2 196 * 197 * Pointer k is the first index of ?-part 198 */ 199 outer: 200 for (int k = less; k <= great; k++) { 201 int ak = a[k]; 202 if (ak < pivot1) { // Move a[k] to left part 203 if (k != less) { 204 a[k] = a[less]; 205 a[less] = ak; 206 } 207 less++; 208 } else if (ak > pivot2) { // Move a[k] to right part 209 while (a[great] > pivot2) { 210 if (great-- == k) { 211 break outer; 212 } 213 } 214 if (a[great] < pivot1) { 215 a[k] = a[less]; 216 a[less++] = a[great]; 217 a[great--] = ak; 218 } else { // pivot1 <= a[great] <= pivot2 219 a[k] = a[great]; 220 a[great--] = ak; 221 } 222 } 223 } 224 } else { // Pivots are equal 225 /* 226 * Partition degenerates to the traditional 3-way, 227 * or "Dutch National Flag", partition: 228 * 229 * left part center part right part 230 * +----------------------------------------------+ 231 * | < pivot | == pivot | ? | > pivot | 232 * +----------------------------------------------+ 233 * ^ ^ ^ 234 * | | | 235 * less k great 236 * 237 * Invariants: 238 * 239 * all in (left, less) < pivot 240 * all in [less, k) == pivot 241 * all in (great, right) > pivot 242 * 243 * Pointer k is the first index of ?-part 244 */ 245 for (int k = less; k <= great; k++) { 246 int ak = a[k]; 247 if (ak == pivot1) { 248 continue; 249 } 250 if (ak < pivot1) { // Move a[k] to left part 251 if (k != less) { 252 a[k] = a[less]; 253 a[less] = ak; 254 } 255 less++; 256 } else { // (a[k] > pivot1) - Move a[k] to right part 257 /* 258 * We know that pivot1 == a[e3] == pivot2. Thus, we know 259 * that great will still be >= k when the following loop 260 * terminates, even though we don't test for it explicitly. 261 * In other words, a[e3] acts as a sentinel for great. 262 */ 263 while (a[great] > pivot1) { 264 great--; 265 } 266 if (a[great] < pivot1) { 267 a[k] = a[less]; 268 a[less++] = a[great]; 269 a[great--] = ak; 270 } else { // a[great] == pivot1 271 a[k] = pivot1; 272 a[great--] = ak; 273 } 274 } 275 } 276 } 277 278 // Swap pivots into their final positions 279 a[left] = a[less - 1]; a[less - 1] = pivot1; 280 a[right] = a[great + 1]; a[great + 1] = pivot2; 281 282 // Sort left and right parts recursively, excluding known pivot values 283 doSort(a, left, less - 2); 284 doSort(a, great + 2, right); 285 286 /* 287 * If pivot1 == pivot2, all elements from center 288 * part are equal and, therefore, already sorted 289 */ 290 if (!pivotsDiffer) { 291 return; 292 } 293 294 /* 295 * If center part is too large (comprises > 2/3 of the array), 296 * swap internal pivot values to ends 297 */ 298 if (less < e1 && great > e5) { 299 while (a[less] == pivot1) { 300 less++; 301 } 302 while (a[great] == pivot2) { 303 great--; 304 } 305 306 /* 307 * Partitioning: 308 * 309 * left part center part right part 310 * +----------------------------------------------------------+ 311 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 312 * +----------------------------------------------------------+ 313 * ^ ^ ^ 314 * | | | 315 * less k great 316 * 317 * Invariants: 318 * 319 * all in (*, less) == pivot1 320 * pivot1 < all in [less, k) < pivot2 321 * all in (great, *) == pivot2 322 * 323 * Pointer k is the first index of ?-part 324 */ 325 outer: 326 for (int k = less; k <= great; k++) { 327 int ak = a[k]; 328 if (ak == pivot2) { // Move a[k] to right part 329 while (a[great] == pivot2) { 330 if (great-- == k) { 331 break outer; 332 } 333 } 334 if (a[great] == pivot1) { 335 a[k] = a[less]; 336 a[less++] = pivot1; 337 } else { // pivot1 < a[great] < pivot2 338 a[k] = a[great]; 339 } 340 a[great--] = pivot2; 341 } else if (ak == pivot1) { // Move a[k] to left part 342 a[k] = a[less]; 343 a[less++] = pivot1; 344 } 345 } 346 } 347 348 // Sort center part recursively, excluding known pivot values 349 doSort(a, less, great); 350 } 351 352 /** 353 * Sorts the specified array into ascending numerical order. 354 * 355 * @param a the array to be sorted 356 */ 357 public static void sort(long[] a) { 358 doSort(a, 0, a.length - 1); 359 } 360 361 /** 362 * Sorts the specified range of the array into ascending order. The range 363 * to be sorted extends from the index {@code fromIndex}, inclusive, to 364 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 365 * the range to be sorted is empty (and the call is a no-op). 366 * 367 * @param a the array to be sorted 368 * @param fromIndex the index of the first element, inclusive, to be sorted 369 * @param toIndex the index of the last element, exclusive, to be sorted 370 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 371 * @throws ArrayIndexOutOfBoundsException 372 * if {@code fromIndex < 0} or {@code toIndex > a.length} 373 */ 374 public static void sort(long[] a, int fromIndex, int toIndex) { 375 rangeCheck(a.length, fromIndex, toIndex); 376 doSort(a, fromIndex, toIndex - 1); 377 } 378 379 /** 380 * Sorts the specified range of the array into ascending order. This 381 * method differs from the public {@code sort} method in that the 382 * {@code right} index is inclusive, and it does no range checking on 383 * {@code left} or {@code right}. 384 * 385 * @param a the array to be sorted 386 * @param left the index of the first element, inclusive, to be sorted 387 * @param right the index of the last element, inclusive, to be sorted 388 */ 389 private static void doSort(long[] a, int left, int right) { 390 // Use insertion sort on tiny arrays 391 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 392 for (int i = left + 1; i <= right; i++) { 393 long ai = a[i]; 394 int j; 395 for (j = i - 1; j >= left && ai < a[j]; j--) { 396 a[j + 1] = a[j]; 397 } 398 a[j + 1] = ai; 399 } 400 } else { // Use Dual-Pivot Quicksort on large arrays 401 dualPivotQuicksort(a, left, right); 402 } 403 } 404 405 /** 406 * Sorts the specified range of the array into ascending order by the 407 * Dual-Pivot Quicksort algorithm. 408 * 409 * @param a the array to be sorted 410 * @param left the index of the first element, inclusive, to be sorted 411 * @param right the index of the last element, inclusive, to be sorted 412 */ 413 private static void dualPivotQuicksort(long[] a, int left, int right) { 414 // Compute indices of five evenly spaced elements 415 int sixth = (right - left + 1) / 6; 416 int e1 = left + sixth; 417 int e5 = right - sixth; 418 int e3 = (left + right) >>> 1; // The midpoint 419 int e4 = e3 + sixth; 420 int e2 = e3 - sixth; 421 422 // Sort these elements using a 5-element sorting network 423 long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 424 425 if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; } 426 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; } 427 if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; } 428 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; } 429 if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; } 430 if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; } 431 if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; } 432 if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; } 433 if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; } 434 435 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 436 437 /* 438 * Use the second and fourth of the five sorted elements as pivots. 439 * These values are inexpensive approximations of the first and 440 * second terciles of the array. Note that pivot1 <= pivot2. 441 * 442 * The pivots are stored in local variables, and the first and 443 * the last of the elements to be sorted are moved to the locations 444 * formerly occupied by the pivots. When partitioning is complete, 445 * the pivots are swapped back into their final positions, and 446 * excluded from subsequent sorting. 447 */ 448 long pivot1 = ae2; a[e2] = a[left]; 449 long pivot2 = ae4; a[e4] = a[right]; 450 451 // Pointers 452 int less = left + 1; // The index of first element of center part 453 int great = right - 1; // The index before first element of right part 454 455 boolean pivotsDiffer = (pivot1 != pivot2); 456 457 if (pivotsDiffer) { 458 /* 459 * Partitioning: 460 * 461 * left part center part right part 462 * +------------------------------------------------------------+ 463 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 464 * +------------------------------------------------------------+ 465 * ^ ^ ^ 466 * | | | 467 * less k great 468 * 469 * Invariants: 470 * 471 * all in (left, less) < pivot1 472 * pivot1 <= all in [less, k) <= pivot2 473 * all in (great, right) > pivot2 474 * 475 * Pointer k is the first index of ?-part 476 */ 477 outer: 478 for (int k = less; k <= great; k++) { 479 long ak = a[k]; 480 if (ak < pivot1) { // Move a[k] to left part 481 if (k != less) { 482 a[k] = a[less]; 483 a[less] = ak; 484 } 485 less++; 486 } else if (ak > pivot2) { // Move a[k] to right part 487 while (a[great] > pivot2) { 488 if (great-- == k) { 489 break outer; 490 } 491 } 492 if (a[great] < pivot1) { 493 a[k] = a[less]; 494 a[less++] = a[great]; 495 a[great--] = ak; 496 } else { // pivot1 <= a[great] <= pivot2 497 a[k] = a[great]; 498 a[great--] = ak; 499 } 500 } 501 } 502 } else { // Pivots are equal 503 /* 504 * Partition degenerates to the traditional 3-way, 505 * or "Dutch National Flag", partition: 506 * 507 * left part center part right part 508 * +----------------------------------------------+ 509 * | < pivot | == pivot | ? | > pivot | 510 * +----------------------------------------------+ 511 * ^ ^ ^ 512 * | | | 513 * less k great 514 * 515 * Invariants: 516 * 517 * all in (left, less) < pivot 518 * all in [less, k) == pivot 519 * all in (great, right) > pivot 520 * 521 * Pointer k is the first index of ?-part 522 */ 523 for (int k = less; k <= great; k++) { 524 long ak = a[k]; 525 if (ak == pivot1) { 526 continue; 527 } 528 if (ak < pivot1) { // Move a[k] to left part 529 if (k != less) { 530 a[k] = a[less]; 531 a[less] = ak; 532 } 533 less++; 534 } else { // (a[k] > pivot1) - Move a[k] to right part 535 /* 536 * We know that pivot1 == a[e3] == pivot2. Thus, we know 537 * that great will still be >= k when the following loop 538 * terminates, even though we don't test for it explicitly. 539 * In other words, a[e3] acts as a sentinel for great. 540 */ 541 while (a[great] > pivot1) { 542 great--; 543 } 544 if (a[great] < pivot1) { 545 a[k] = a[less]; 546 a[less++] = a[great]; 547 a[great--] = ak; 548 } else { // a[great] == pivot1 549 a[k] = pivot1; 550 a[great--] = ak; 551 } 552 } 553 } 554 } 555 556 // Swap pivots into their final positions 557 a[left] = a[less - 1]; a[less - 1] = pivot1; 558 a[right] = a[great + 1]; a[great + 1] = pivot2; 559 560 // Sort left and right parts recursively, excluding known pivot values 561 doSort(a, left, less - 2); 562 doSort(a, great + 2, right); 563 564 /* 565 * If pivot1 == pivot2, all elements from center 566 * part are equal and, therefore, already sorted 567 */ 568 if (!pivotsDiffer) { 569 return; 570 } 571 572 /* 573 * If center part is too large (comprises > 2/3 of the array), 574 * swap internal pivot values to ends 575 */ 576 if (less < e1 && great > e5) { 577 while (a[less] == pivot1) { 578 less++; 579 } 580 while (a[great] == pivot2) { 581 great--; 582 } 583 584 /* 585 * Partitioning: 586 * 587 * left part center part right part 588 * +----------------------------------------------------------+ 589 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 590 * +----------------------------------------------------------+ 591 * ^ ^ ^ 592 * | | | 593 * less k great 594 * 595 * Invariants: 596 * 597 * all in (*, less) == pivot1 598 * pivot1 < all in [less, k) < pivot2 599 * all in (great, *) == pivot2 600 * 601 * Pointer k is the first index of ?-part 602 */ 603 outer: 604 for (int k = less; k <= great; k++) { 605 long ak = a[k]; 606 if (ak == pivot2) { // Move a[k] to right part 607 while (a[great] == pivot2) { 608 if (great-- == k) { 609 break outer; 610 } 611 } 612 if (a[great] == pivot1) { 613 a[k] = a[less]; 614 a[less++] = pivot1; 615 } else { // pivot1 < a[great] < pivot2 616 a[k] = a[great]; 617 } 618 a[great--] = pivot2; 619 } else if (ak == pivot1) { // Move a[k] to left part 620 a[k] = a[less]; 621 a[less++] = pivot1; 622 } 623 } 624 } 625 626 // Sort center part recursively, excluding known pivot values 627 doSort(a, less, great); 628 } 629 630 /** 631 * Sorts the specified array into ascending numerical order. 632 * 633 * @param a the array to be sorted 634 */ 635 public static void sort(short[] a) { 636 doSort(a, 0, a.length - 1); 637 } 638 639 /** 640 * Sorts the specified range of the array into ascending order. The range 641 * to be sorted extends from the index {@code fromIndex}, inclusive, to 642 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 643 * the range to be sorted is empty (and the call is a no-op). 644 * 645 * @param a the array to be sorted 646 * @param fromIndex the index of the first element, inclusive, to be sorted 647 * @param toIndex the index of the last element, exclusive, to be sorted 648 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 649 * @throws ArrayIndexOutOfBoundsException 650 * if {@code fromIndex < 0} or {@code toIndex > a.length} 651 */ 652 public static void sort(short[] a, int fromIndex, int toIndex) { 653 rangeCheck(a.length, fromIndex, toIndex); 654 doSort(a, fromIndex, toIndex - 1); 655 } 656 657 /** The number of distinct short values. */ 658 private static final int NUM_SHORT_VALUES = 1 << 16; 659 660 /** 661 * Sorts the specified range of the array into ascending order. This 662 * method differs from the public {@code sort} method in that the 663 * {@code right} index is inclusive, and it does no range checking on 664 * {@code left} or {@code right}. 665 * 666 * @param a the array to be sorted 667 * @param left the index of the first element, inclusive, to be sorted 668 * @param right the index of the last element, inclusive, to be sorted 669 */ 670 private static void doSort(short[] a, int left, int right) { 671 // Use insertion sort on tiny arrays 672 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 673 for (int i = left + 1; i <= right; i++) { 674 short ai = a[i]; 675 int j; 676 for (j = i - 1; j >= left && ai < a[j]; j--) { 677 a[j + 1] = a[j]; 678 } 679 a[j + 1] = ai; 680 } 681 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { 682 // Use counting sort on huge arrays 683 int[] count = new int[NUM_SHORT_VALUES]; 684 685 for (int i = left; i <= right; i++) { 686 count[a[i] - Short.MIN_VALUE]++; 687 } 688 for (int i = 0, k = left; i < count.length && k <= right; i++) { 689 short value = (short) (i + Short.MIN_VALUE); 690 691 for (int s = count[i]; s > 0; s--) { 692 a[k++] = value; 693 } 694 } 695 } else { // Use Dual-Pivot Quicksort on large arrays 696 dualPivotQuicksort(a, left, right); 697 } 698 } 699 700 /** 701 * Sorts the specified range of the array into ascending order by the 702 * Dual-Pivot Quicksort algorithm. 703 * 704 * @param a the array to be sorted 705 * @param left the index of the first element, inclusive, to be sorted 706 * @param right the index of the last element, inclusive, to be sorted 707 */ 708 private static void dualPivotQuicksort(short[] a, int left, int right) { 709 // Compute indices of five evenly spaced elements 710 int sixth = (right - left + 1) / 6; 711 int e1 = left + sixth; 712 int e5 = right - sixth; 713 int e3 = (left + right) >>> 1; // The midpoint 714 int e4 = e3 + sixth; 715 int e2 = e3 - sixth; 716 717 // Sort these elements using a 5-element sorting network 718 short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 719 720 if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; } 721 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; } 722 if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; } 723 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; } 724 if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; } 725 if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; } 726 if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; } 727 if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; } 728 if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; } 729 730 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 731 732 /* 733 * Use the second and fourth of the five sorted elements as pivots. 734 * These values are inexpensive approximations of the first and 735 * second terciles of the array. Note that pivot1 <= pivot2. 736 * 737 * The pivots are stored in local variables, and the first and 738 * the last of the elements to be sorted are moved to the locations 739 * formerly occupied by the pivots. When partitioning is complete, 740 * the pivots are swapped back into their final positions, and 741 * excluded from subsequent sorting. 742 */ 743 short pivot1 = ae2; a[e2] = a[left]; 744 short pivot2 = ae4; a[e4] = a[right]; 745 746 // Pointers 747 int less = left + 1; // The index of first element of center part 748 int great = right - 1; // The index before first element of right part 749 750 boolean pivotsDiffer = (pivot1 != pivot2); 751 752 if (pivotsDiffer) { 753 /* 754 * Partitioning: 755 * 756 * left part center part right part 757 * +------------------------------------------------------------+ 758 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 759 * +------------------------------------------------------------+ 760 * ^ ^ ^ 761 * | | | 762 * less k great 763 * 764 * Invariants: 765 * 766 * all in (left, less) < pivot1 767 * pivot1 <= all in [less, k) <= pivot2 768 * all in (great, right) > pivot2 769 * 770 * Pointer k is the first index of ?-part 771 */ 772 outer: 773 for (int k = less; k <= great; k++) { 774 short ak = a[k]; 775 if (ak < pivot1) { // Move a[k] to left part 776 if (k != less) { 777 a[k] = a[less]; 778 a[less] = ak; 779 } 780 less++; 781 } else if (ak > pivot2) { // Move a[k] to right part 782 while (a[great] > pivot2) { 783 if (great-- == k) { 784 break outer; 785 } 786 } 787 if (a[great] < pivot1) { 788 a[k] = a[less]; 789 a[less++] = a[great]; 790 a[great--] = ak; 791 } else { // pivot1 <= a[great] <= pivot2 792 a[k] = a[great]; 793 a[great--] = ak; 794 } 795 } 796 } 797 } else { // Pivots are equal 798 /* 799 * Partition degenerates to the traditional 3-way, 800 * or "Dutch National Flag", partition: 801 * 802 * left part center part right part 803 * +----------------------------------------------+ 804 * | < pivot | == pivot | ? | > pivot | 805 * +----------------------------------------------+ 806 * ^ ^ ^ 807 * | | | 808 * less k great 809 * 810 * Invariants: 811 * 812 * all in (left, less) < pivot 813 * all in [less, k) == pivot 814 * all in (great, right) > pivot 815 * 816 * Pointer k is the first index of ?-part 817 */ 818 for (int k = less; k <= great; k++) { 819 short ak = a[k]; 820 if (ak == pivot1) { 821 continue; 822 } 823 if (ak < pivot1) { // Move a[k] to left part 824 if (k != less) { 825 a[k] = a[less]; 826 a[less] = ak; 827 } 828 less++; 829 } else { // (a[k] > pivot1) - Move a[k] to right part 830 /* 831 * We know that pivot1 == a[e3] == pivot2. Thus, we know 832 * that great will still be >= k when the following loop 833 * terminates, even though we don't test for it explicitly. 834 * In other words, a[e3] acts as a sentinel for great. 835 */ 836 while (a[great] > pivot1) { 837 great--; 838 } 839 if (a[great] < pivot1) { 840 a[k] = a[less]; 841 a[less++] = a[great]; 842 a[great--] = ak; 843 } else { // a[great] == pivot1 844 a[k] = pivot1; 845 a[great--] = ak; 846 } 847 } 848 } 849 } 850 851 // Swap pivots into their final positions 852 a[left] = a[less - 1]; a[less - 1] = pivot1; 853 a[right] = a[great + 1]; a[great + 1] = pivot2; 854 855 // Sort left and right parts recursively, excluding known pivot values 856 doSort(a, left, less - 2); 857 doSort(a, great + 2, right); 858 859 /* 860 * If pivot1 == pivot2, all elements from center 861 * part are equal and, therefore, already sorted 862 */ 863 if (!pivotsDiffer) { 864 return; 865 } 866 867 /* 868 * If center part is too large (comprises > 2/3 of the array), 869 * swap internal pivot values to ends 870 */ 871 if (less < e1 && great > e5) { 872 while (a[less] == pivot1) { 873 less++; 874 } 875 while (a[great] == pivot2) { 876 great--; 877 } 878 879 /* 880 * Partitioning: 881 * 882 * left part center part right part 883 * +----------------------------------------------------------+ 884 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 885 * +----------------------------------------------------------+ 886 * ^ ^ ^ 887 * | | | 888 * less k great 889 * 890 * Invariants: 891 * 892 * all in (*, less) == pivot1 893 * pivot1 < all in [less, k) < pivot2 894 * all in (great, *) == pivot2 895 * 896 * Pointer k is the first index of ?-part 897 */ 898 outer: 899 for (int k = less; k <= great; k++) { 900 short ak = a[k]; 901 if (ak == pivot2) { // Move a[k] to right part 902 while (a[great] == pivot2) { 903 if (great-- == k) { 904 break outer; 905 } 906 } 907 if (a[great] == pivot1) { 908 a[k] = a[less]; 909 a[less++] = pivot1; 910 } else { // pivot1 < a[great] < pivot2 911 a[k] = a[great]; 912 } 913 a[great--] = pivot2; 914 } else if (ak == pivot1) { // Move a[k] to left part 915 a[k] = a[less]; 916 a[less++] = pivot1; 917 } 918 } 919 } 920 921 // Sort center part recursively, excluding known pivot values 922 doSort(a, less, great); 923 } 924 925 /** 926 * Sorts the specified array into ascending numerical order. 927 * 928 * @param a the array to be sorted 929 */ 930 public static void sort(char[] a) { 931 doSort(a, 0, a.length - 1); 932 } 933 934 /** 935 * Sorts the specified range of the array into ascending order. The range 936 * to be sorted extends from the index {@code fromIndex}, inclusive, to 937 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 938 * the range to be sorted is empty (and the call is a no-op). 939 * 940 * @param a the array to be sorted 941 * @param fromIndex the index of the first element, inclusive, to be sorted 942 * @param toIndex the index of the last element, exclusive, to be sorted 943 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 944 * @throws ArrayIndexOutOfBoundsException 945 * if {@code fromIndex < 0} or {@code toIndex > a.length} 946 */ 947 public static void sort(char[] a, int fromIndex, int toIndex) { 948 rangeCheck(a.length, fromIndex, toIndex); 949 doSort(a, fromIndex, toIndex - 1); 950 } 951 952 /** The number of distinct char values. */ 953 private static final int NUM_CHAR_VALUES = 1 << 16; 954 955 /** 956 * Sorts the specified range of the array into ascending order. This 957 * method differs from the public {@code sort} method in that the 958 * {@code right} index is inclusive, and it does no range checking on 959 * {@code left} or {@code right}. 960 * 961 * @param a the array to be sorted 962 * @param left the index of the first element, inclusive, to be sorted 963 * @param right the index of the last element, inclusive, to be sorted 964 */ 965 private static void doSort(char[] a, int left, int right) { 966 // Use insertion sort on tiny arrays 967 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 968 for (int i = left + 1; i <= right; i++) { 969 char ai = a[i]; 970 int j; 971 for (j = i - 1; j >= left && ai < a[j]; j--) { 972 a[j + 1] = a[j]; 973 } 974 a[j + 1] = ai; 975 } 976 } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { 977 // Use counting sort on huge arrays 978 int[] count = new int[NUM_CHAR_VALUES]; 979 980 for (int i = left; i <= right; i++) { 981 count[a[i]]++; 982 } 983 for (int i = 0, k = left; i < count.length && k <= right; i++) { 984 for (int s = count[i]; s > 0; s--) { 985 a[k++] = (char) i; 986 } 987 } 988 } else { // Use Dual-Pivot Quicksort on large arrays 989 dualPivotQuicksort(a, left, right); 990 } 991 } 992 993 /** 994 * Sorts the specified range of the array into ascending order by the 995 * Dual-Pivot Quicksort algorithm. 996 * 997 * @param a the array to be sorted 998 * @param left the index of the first element, inclusive, to be sorted 999 * @param right the index of the last element, inclusive, to be sorted 1000 */ 1001 private static void dualPivotQuicksort(char[] a, int left, int right) { 1002 // Compute indices of five evenly spaced elements 1003 int sixth = (right - left + 1) / 6; 1004 int e1 = left + sixth; 1005 int e5 = right - sixth; 1006 int e3 = (left + right) >>> 1; // The midpoint 1007 int e4 = e3 + sixth; 1008 int e2 = e3 - sixth; 1009 1010 // Sort these elements using a 5-element sorting network 1011 char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 1012 1013 if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; } 1014 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; } 1015 if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; } 1016 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; } 1017 if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; } 1018 if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; } 1019 if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; } 1020 if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; } 1021 if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; } 1022 1023 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 1024 1025 /* 1026 * Use the second and fourth of the five sorted elements as pivots. 1027 * These values are inexpensive approximations of the first and 1028 * second terciles of the array. Note that pivot1 <= pivot2. 1029 * 1030 * The pivots are stored in local variables, and the first and 1031 * the last of the elements to be sorted are moved to the locations 1032 * formerly occupied by the pivots. When partitioning is complete, 1033 * the pivots are swapped back into their final positions, and 1034 * excluded from subsequent sorting. 1035 */ 1036 char pivot1 = ae2; a[e2] = a[left]; 1037 char pivot2 = ae4; a[e4] = a[right]; 1038 1039 // Pointers 1040 int less = left + 1; // The index of first element of center part 1041 int great = right - 1; // The index before first element of right part 1042 1043 boolean pivotsDiffer = (pivot1 != pivot2); 1044 1045 if (pivotsDiffer) { 1046 /* 1047 * Partitioning: 1048 * 1049 * left part center part right part 1050 * +------------------------------------------------------------+ 1051 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 1052 * +------------------------------------------------------------+ 1053 * ^ ^ ^ 1054 * | | | 1055 * less k great 1056 * 1057 * Invariants: 1058 * 1059 * all in (left, less) < pivot1 1060 * pivot1 <= all in [less, k) <= pivot2 1061 * all in (great, right) > pivot2 1062 * 1063 * Pointer k is the first index of ?-part 1064 */ 1065 outer: 1066 for (int k = less; k <= great; k++) { 1067 char ak = a[k]; 1068 if (ak < pivot1) { // Move a[k] to left part 1069 if (k != less) { 1070 a[k] = a[less]; 1071 a[less] = ak; 1072 } 1073 less++; 1074 } else if (ak > pivot2) { // Move a[k] to right part 1075 while (a[great] > pivot2) { 1076 if (great-- == k) { 1077 break outer; 1078 } 1079 } 1080 if (a[great] < pivot1) { 1081 a[k] = a[less]; 1082 a[less++] = a[great]; 1083 a[great--] = ak; 1084 } else { // pivot1 <= a[great] <= pivot2 1085 a[k] = a[great]; 1086 a[great--] = ak; 1087 } 1088 } 1089 } 1090 } else { // Pivots are equal 1091 /* 1092 * Partition degenerates to the traditional 3-way, 1093 * or "Dutch National Flag", partition: 1094 * 1095 * left part center part right part 1096 * +----------------------------------------------+ 1097 * | < pivot | == pivot | ? | > pivot | 1098 * +----------------------------------------------+ 1099 * ^ ^ ^ 1100 * | | | 1101 * less k great 1102 * 1103 * Invariants: 1104 * 1105 * all in (left, less) < pivot 1106 * all in [less, k) == pivot 1107 * all in (great, right) > pivot 1108 * 1109 * Pointer k is the first index of ?-part 1110 */ 1111 for (int k = less; k <= great; k++) { 1112 char ak = a[k]; 1113 if (ak == pivot1) { 1114 continue; 1115 } 1116 if (ak < pivot1) { // Move a[k] to left part 1117 if (k != less) { 1118 a[k] = a[less]; 1119 a[less] = ak; 1120 } 1121 less++; 1122 } else { // (a[k] > pivot1) - Move a[k] to right part 1123 /* 1124 * We know that pivot1 == a[e3] == pivot2. Thus, we know 1125 * that great will still be >= k when the following loop 1126 * terminates, even though we don't test for it explicitly. 1127 * In other words, a[e3] acts as a sentinel for great. 1128 */ 1129 while (a[great] > pivot1) { 1130 great--; 1131 } 1132 if (a[great] < pivot1) { 1133 a[k] = a[less]; 1134 a[less++] = a[great]; 1135 a[great--] = ak; 1136 } else { // a[great] == pivot1 1137 a[k] = pivot1; 1138 a[great--] = ak; 1139 } 1140 } 1141 } 1142 } 1143 1144 // Swap pivots into their final positions 1145 a[left] = a[less - 1]; a[less - 1] = pivot1; 1146 a[right] = a[great + 1]; a[great + 1] = pivot2; 1147 1148 // Sort left and right parts recursively, excluding known pivot values 1149 doSort(a, left, less - 2); 1150 doSort(a, great + 2, right); 1151 1152 /* 1153 * If pivot1 == pivot2, all elements from center 1154 * part are equal and, therefore, already sorted 1155 */ 1156 if (!pivotsDiffer) { 1157 return; 1158 } 1159 1160 /* 1161 * If center part is too large (comprises > 2/3 of the array), 1162 * swap internal pivot values to ends 1163 */ 1164 if (less < e1 && great > e5) { 1165 while (a[less] == pivot1) { 1166 less++; 1167 } 1168 while (a[great] == pivot2) { 1169 great--; 1170 } 1171 1172 /* 1173 * Partitioning: 1174 * 1175 * left part center part right part 1176 * +----------------------------------------------------------+ 1177 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 1178 * +----------------------------------------------------------+ 1179 * ^ ^ ^ 1180 * | | | 1181 * less k great 1182 * 1183 * Invariants: 1184 * 1185 * all in (*, less) == pivot1 1186 * pivot1 < all in [less, k) < pivot2 1187 * all in (great, *) == pivot2 1188 * 1189 * Pointer k is the first index of ?-part 1190 */ 1191 outer: 1192 for (int k = less; k <= great; k++) { 1193 char ak = a[k]; 1194 if (ak == pivot2) { // Move a[k] to right part 1195 while (a[great] == pivot2) { 1196 if (great-- == k) { 1197 break outer; 1198 } 1199 } 1200 if (a[great] == pivot1) { 1201 a[k] = a[less]; 1202 a[less++] = pivot1; 1203 } else { // pivot1 < a[great] < pivot2 1204 a[k] = a[great]; 1205 } 1206 a[great--] = pivot2; 1207 } else if (ak == pivot1) { // Move a[k] to left part 1208 a[k] = a[less]; 1209 a[less++] = pivot1; 1210 } 1211 } 1212 } 1213 1214 // Sort center part recursively, excluding known pivot values 1215 doSort(a, less, great); 1216 } 1217 1218 /** 1219 * Sorts the specified array into ascending numerical order. 1220 * 1221 * @param a the array to be sorted 1222 */ 1223 public static void sort(byte[] a) { 1224 doSort(a, 0, a.length - 1); 1225 } 1226 1227 /** 1228 * Sorts the specified range of the array into ascending order. The range 1229 * to be sorted extends from the index {@code fromIndex}, inclusive, to 1230 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 1231 * the range to be sorted is empty (and the call is a no-op). 1232 * 1233 * @param a the array to be sorted 1234 * @param fromIndex the index of the first element, inclusive, to be sorted 1235 * @param toIndex the index of the last element, exclusive, to be sorted 1236 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1237 * @throws ArrayIndexOutOfBoundsException 1238 * if {@code fromIndex < 0} or {@code toIndex > a.length} 1239 */ 1240 public static void sort(byte[] a, int fromIndex, int toIndex) { 1241 rangeCheck(a.length, fromIndex, toIndex); 1242 doSort(a, fromIndex, toIndex - 1); 1243 } 1244 1245 /** The number of distinct byte values. */ 1246 private static final int NUM_BYTE_VALUES = 1 << 8; 1247 1248 /** 1249 * Sorts the specified range of the array into ascending order. This 1250 * method differs from the public {@code sort} method in that the 1251 * {@code right} index is inclusive, and it does no range checking on 1252 * {@code left} or {@code right}. 1253 * 1254 * @param a the array to be sorted 1255 * @param left the index of the first element, inclusive, to be sorted 1256 * @param right the index of the last element, inclusive, to be sorted 1257 */ 1258 private static void doSort(byte[] a, int left, int right) { 1259 // Use insertion sort on tiny arrays 1260 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 1261 for (int i = left + 1; i <= right; i++) { 1262 byte ai = a[i]; 1263 int j; 1264 for (j = i - 1; j >= left && ai < a[j]; j--) { 1265 a[j + 1] = a[j]; 1266 } 1267 a[j + 1] = ai; 1268 } 1269 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) { 1270 // Use counting sort on huge arrays 1271 int[] count = new int[NUM_BYTE_VALUES]; 1272 1273 for (int i = left; i <= right; i++) { 1274 count[a[i] - Byte.MIN_VALUE]++; 1275 } 1276 for (int i = 0, k = left; i < count.length && k <= right; i++) { 1277 byte value = (byte) (i + Byte.MIN_VALUE); 1278 1279 for (int s = count[i]; s > 0; s--) { 1280 a[k++] = value; 1281 } 1282 } 1283 } else { // Use Dual-Pivot Quicksort on large arrays 1284 dualPivotQuicksort(a, left, right); 1285 } 1286 } 1287 1288 /** 1289 * Sorts the specified range of the array into ascending order by the 1290 * Dual-Pivot Quicksort algorithm. 1291 * 1292 * @param a the array to be sorted 1293 * @param left the index of the first element, inclusive, to be sorted 1294 * @param right the index of the last element, inclusive, to be sorted 1295 */ 1296 private static void dualPivotQuicksort(byte[] a, int left, int right) { 1297 // Compute indices of five evenly spaced elements 1298 int sixth = (right - left + 1) / 6; 1299 int e1 = left + sixth; 1300 int e5 = right - sixth; 1301 int e3 = (left + right) >>> 1; // The midpoint 1302 int e4 = e3 + sixth; 1303 int e2 = e3 - sixth; 1304 1305 // Sort these elements using a 5-element sorting network 1306 byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 1307 1308 if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; } 1309 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; } 1310 if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; } 1311 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; } 1312 if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; } 1313 if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; } 1314 if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; } 1315 if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; } 1316 if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; } 1317 1318 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 1319 1320 /* 1321 * Use the second and fourth of the five sorted elements as pivots. 1322 * These values are inexpensive approximations of the first and 1323 * second terciles of the array. Note that pivot1 <= pivot2. 1324 * 1325 * The pivots are stored in local variables, and the first and 1326 * the last of the elements to be sorted are moved to the locations 1327 * formerly occupied by the pivots. When partitioning is complete, 1328 * the pivots are swapped back into their final positions, and 1329 * excluded from subsequent sorting. 1330 */ 1331 byte pivot1 = ae2; a[e2] = a[left]; 1332 byte pivot2 = ae4; a[e4] = a[right]; 1333 1334 // Pointers 1335 int less = left + 1; // The index of first element of center part 1336 int great = right - 1; // The index before first element of right part 1337 1338 boolean pivotsDiffer = (pivot1 != pivot2); 1339 1340 if (pivotsDiffer) { 1341 /* 1342 * Partitioning: 1343 * 1344 * left part center part right part 1345 * +------------------------------------------------------------+ 1346 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 1347 * +------------------------------------------------------------+ 1348 * ^ ^ ^ 1349 * | | | 1350 * less k great 1351 * 1352 * Invariants: 1353 * 1354 * all in (left, less) < pivot1 1355 * pivot1 <= all in [less, k) <= pivot2 1356 * all in (great, right) > pivot2 1357 * 1358 * Pointer k is the first index of ?-part 1359 */ 1360 outer: 1361 for (int k = less; k <= great; k++) { 1362 byte ak = a[k]; 1363 if (ak < pivot1) { // Move a[k] to left part 1364 if (k != less) { 1365 a[k] = a[less]; 1366 a[less] = ak; 1367 } 1368 less++; 1369 } else if (ak > pivot2) { // Move a[k] to right part 1370 while (a[great] > pivot2) { 1371 if (great-- == k) { 1372 break outer; 1373 } 1374 } 1375 if (a[great] < pivot1) { 1376 a[k] = a[less]; 1377 a[less++] = a[great]; 1378 a[great--] = ak; 1379 } else { // pivot1 <= a[great] <= pivot2 1380 a[k] = a[great]; 1381 a[great--] = ak; 1382 } 1383 } 1384 } 1385 } else { // Pivots are equal 1386 /* 1387 * Partition degenerates to the traditional 3-way, 1388 * or "Dutch National Flag", partition: 1389 * 1390 * left part center part right part 1391 * +----------------------------------------------+ 1392 * | < pivot | == pivot | ? | > pivot | 1393 * +----------------------------------------------+ 1394 * ^ ^ ^ 1395 * | | | 1396 * less k great 1397 * 1398 * Invariants: 1399 * 1400 * all in (left, less) < pivot 1401 * all in [less, k) == pivot 1402 * all in (great, right) > pivot 1403 * 1404 * Pointer k is the first index of ?-part 1405 */ 1406 for (int k = less; k <= great; k++) { 1407 byte ak = a[k]; 1408 if (ak == pivot1) { 1409 continue; 1410 } 1411 if (ak < pivot1) { // Move a[k] to left part 1412 if (k != less) { 1413 a[k] = a[less]; 1414 a[less] = ak; 1415 } 1416 less++; 1417 } else { // (a[k] > pivot1) - Move a[k] to right part 1418 /* 1419 * We know that pivot1 == a[e3] == pivot2. Thus, we know 1420 * that great will still be >= k when the following loop 1421 * terminates, even though we don't test for it explicitly. 1422 * In other words, a[e3] acts as a sentinel for great. 1423 */ 1424 while (a[great] > pivot1) { 1425 great--; 1426 } 1427 if (a[great] < pivot1) { 1428 a[k] = a[less]; 1429 a[less++] = a[great]; 1430 a[great--] = ak; 1431 } else { // a[great] == pivot1 1432 a[k] = pivot1; 1433 a[great--] = ak; 1434 } 1435 } 1436 } 1437 } 1438 1439 // Swap pivots into their final positions 1440 a[left] = a[less - 1]; a[less - 1] = pivot1; 1441 a[right] = a[great + 1]; a[great + 1] = pivot2; 1442 1443 // Sort left and right parts recursively, excluding known pivot values 1444 doSort(a, left, less - 2); 1445 doSort(a, great + 2, right); 1446 1447 /* 1448 * If pivot1 == pivot2, all elements from center 1449 * part are equal and, therefore, already sorted 1450 */ 1451 if (!pivotsDiffer) { 1452 return; 1453 } 1454 1455 /* 1456 * If center part is too large (comprises > 2/3 of the array), 1457 * swap internal pivot values to ends 1458 */ 1459 if (less < e1 && great > e5) { 1460 while (a[less] == pivot1) { 1461 less++; 1462 } 1463 while (a[great] == pivot2) { 1464 great--; 1465 } 1466 1467 /* 1468 * Partitioning: 1469 * 1470 * left part center part right part 1471 * +----------------------------------------------------------+ 1472 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 1473 * +----------------------------------------------------------+ 1474 * ^ ^ ^ 1475 * | | | 1476 * less k great 1477 * 1478 * Invariants: 1479 * 1480 * all in (*, less) == pivot1 1481 * pivot1 < all in [less, k) < pivot2 1482 * all in (great, *) == pivot2 1483 * 1484 * Pointer k is the first index of ?-part 1485 */ 1486 outer: 1487 for (int k = less; k <= great; k++) { 1488 byte ak = a[k]; 1489 if (ak == pivot2) { // Move a[k] to right part 1490 while (a[great] == pivot2) { 1491 if (great-- == k) { 1492 break outer; 1493 } 1494 } 1495 if (a[great] == pivot1) { 1496 a[k] = a[less]; 1497 a[less++] = pivot1; 1498 } else { // pivot1 < a[great] < pivot2 1499 a[k] = a[great]; 1500 } 1501 a[great--] = pivot2; 1502 } else if (ak == pivot1) { // Move a[k] to left part 1503 a[k] = a[less]; 1504 a[less++] = pivot1; 1505 } 1506 } 1507 } 1508 1509 // Sort center part recursively, excluding known pivot values 1510 doSort(a, less, great); 1511 } 1512 1513 /** 1514 * Sorts the specified array into ascending numerical order. 1515 * 1516 * <p>The {@code <} relation does not provide a total order on all float 1517 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 1518 * value compares neither less than, greater than, nor equal to any value, 1519 * even itself. This method uses the total order imposed by the method 1520 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 1521 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 1522 * other value and all {@code Float.NaN} values are considered equal. 1523 * 1524 * @param a the array to be sorted 1525 */ 1526 public static void sort(float[] a) { 1527 sortNegZeroAndNaN(a, 0, a.length - 1); 1528 } 1529 1530 /** 1531 * Sorts the specified range of the array into ascending order. The range 1532 * to be sorted extends from the index {@code fromIndex}, inclusive, to 1533 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 1534 * the range to be sorted is empty and the call is a no-op). 1535 * 1536 * <p>The {@code <} relation does not provide a total order on all float 1537 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 1538 * value compares neither less than, greater than, nor equal to any value, 1539 * even itself. This method uses the total order imposed by the method 1540 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 1541 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 1542 * other value and all {@code Float.NaN} values are considered equal. 1543 * 1544 * @param a the array to be sorted 1545 * @param fromIndex the index of the first element, inclusive, to be sorted 1546 * @param toIndex the index of the last element, exclusive, to be sorted 1547 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1548 * @throws ArrayIndexOutOfBoundsException 1549 * if {@code fromIndex < 0} or {@code toIndex > a.length} 1550 */ 1551 public static void sort(float[] a, int fromIndex, int toIndex) { 1552 rangeCheck(a.length, fromIndex, toIndex); 1553 sortNegZeroAndNaN(a, fromIndex, toIndex - 1); 1554 } 1555 1556 /** 1557 * Sorts the specified range of the array into ascending order. The 1558 * sort is done in three phases to avoid expensive comparisons in the 1559 * inner loop. The comparisons would be expensive due to anomalies 1560 * associated with negative zero {@code -0.0f} and {@code Float.NaN}. 1561 * 1562 * @param a the array to be sorted 1563 * @param left the index of the first element, inclusive, to be sorted 1564 * @param right the index of the last element, inclusive, to be sorted 1565 */ 1566 private static void sortNegZeroAndNaN(float[] a, int left, int right) { 1567 /* 1568 * Phase 1: Count negative zeros and move NaNs to end of array 1569 */ 1570 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f); 1571 int numNegativeZeros = 0; 1572 int n = right; 1573 1574 for (int k = left; k <= n; k++) { 1575 float ak = a[k]; 1576 if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) { 1577 a[k] = 0.0f; 1578 numNegativeZeros++; 1579 } else if (ak != ak) { // i.e., ak is NaN 1580 a[k--] = a[n]; 1581 a[n--] = Float.NaN; 1582 } 1583 } 1584 1585 /* 1586 * Phase 2: Sort everything except NaNs (which are already in place) 1587 */ 1588 doSort(a, left, n); 1589 1590 /* 1591 * Phase 3: Turn positive zeros back into negative zeros as appropriate 1592 */ 1593 if (numNegativeZeros == 0) { 1594 return; 1595 } 1596 1597 // Find first zero element 1598 int zeroIndex = findAnyZero(a, left, n); 1599 1600 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) { 1601 zeroIndex = i; 1602 } 1603 1604 // Turn the right number of positive zeros back into negative zeros 1605 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) { 1606 a[i] = -0.0f; 1607 } 1608 } 1609 1610 /** 1611 * Returns the index of some zero element in the specified range via 1612 * binary search. The range is assumed to be sorted, and must contain 1613 * at least one zero. 1614 * 1615 * @param a the array to be searched 1616 * @param low the index of the first element, inclusive, to be searched 1617 * @param high the index of the last element, inclusive, to be searched 1618 */ 1619 private static int findAnyZero(float[] a, int low, int high) { 1620 while (true) { 1621 int middle = (low + high) >>> 1; 1622 float middleValue = a[middle]; 1623 1624 if (middleValue < 0.0f) { 1625 low = middle + 1; 1626 } else if (middleValue > 0.0f) { 1627 high = middle - 1; 1628 } else { // middleValue == 0.0f 1629 return middle; 1630 } 1631 } 1632 } 1633 1634 /** 1635 * Sorts the specified range of the array into ascending order. This 1636 * method differs from the public {@code sort} method in three ways: 1637 * {@code right} index is inclusive, it does no range checking on 1638 * {@code left} or {@code right}, and it does not handle negative 1639 * zeros or NaNs in the array. 1640 * 1641 * @param a the array to be sorted, which must not contain -0.0f or NaN 1642 * @param left the index of the first element, inclusive, to be sorted 1643 * @param right the index of the last element, inclusive, to be sorted 1644 */ 1645 private static void doSort(float[] a, int left, int right) { 1646 // Use insertion sort on tiny arrays 1647 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 1648 for (int i = left + 1; i <= right; i++) { 1649 float ai = a[i]; 1650 int j; 1651 for (j = i - 1; j >= left && ai < a[j]; j--) { 1652 a[j + 1] = a[j]; 1653 } 1654 a[j + 1] = ai; 1655 } 1656 } else { // Use Dual-Pivot Quicksort on large arrays 1657 dualPivotQuicksort(a, left, right); 1658 } 1659 } 1660 1661 /** 1662 * Sorts the specified range of the array into ascending order by the 1663 * Dual-Pivot Quicksort algorithm. 1664 * 1665 * @param a the array to be sorted 1666 * @param left the index of the first element, inclusive, to be sorted 1667 * @param right the index of the last element, inclusive, to be sorted 1668 */ 1669 private static void dualPivotQuicksort(float[] a, int left, int right) { 1670 // Compute indices of five evenly spaced elements 1671 int sixth = (right - left + 1) / 6; 1672 int e1 = left + sixth; 1673 int e5 = right - sixth; 1674 int e3 = (left + right) >>> 1; // The midpoint 1675 int e4 = e3 + sixth; 1676 int e2 = e3 - sixth; 1677 1678 // Sort these elements using a 5-element sorting network 1679 float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 1680 1681 if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; } 1682 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; } 1683 if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; } 1684 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; } 1685 if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; } 1686 if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; } 1687 if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; } 1688 if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; } 1689 if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; } 1690 1691 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 1692 1693 /* 1694 * Use the second and fourth of the five sorted elements as pivots. 1695 * These values are inexpensive approximations of the first and 1696 * second terciles of the array. Note that pivot1 <= pivot2. 1697 * 1698 * The pivots are stored in local variables, and the first and 1699 * the last of the elements to be sorted are moved to the locations 1700 * formerly occupied by the pivots. When partitioning is complete, 1701 * the pivots are swapped back into their final positions, and 1702 * excluded from subsequent sorting. 1703 */ 1704 float pivot1 = ae2; a[e2] = a[left]; 1705 float pivot2 = ae4; a[e4] = a[right]; 1706 1707 // Pointers 1708 int less = left + 1; // The index of first element of center part 1709 int great = right - 1; // The index before first element of right part 1710 1711 boolean pivotsDiffer = (pivot1 != pivot2); 1712 1713 if (pivotsDiffer) { 1714 /* 1715 * Partitioning: 1716 * 1717 * left part center part right part 1718 * +------------------------------------------------------------+ 1719 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 1720 * +------------------------------------------------------------+ 1721 * ^ ^ ^ 1722 * | | | 1723 * less k great 1724 * 1725 * Invariants: 1726 * 1727 * all in (left, less) < pivot1 1728 * pivot1 <= all in [less, k) <= pivot2 1729 * all in (great, right) > pivot2 1730 * 1731 * Pointer k is the first index of ?-part 1732 */ 1733 outer: 1734 for (int k = less; k <= great; k++) { 1735 float ak = a[k]; 1736 if (ak < pivot1) { // Move a[k] to left part 1737 if (k != less) { 1738 a[k] = a[less]; 1739 a[less] = ak; 1740 } 1741 less++; 1742 } else if (ak > pivot2) { // Move a[k] to right part 1743 while (a[great] > pivot2) { 1744 if (great-- == k) { 1745 break outer; 1746 } 1747 } 1748 if (a[great] < pivot1) { 1749 a[k] = a[less]; 1750 a[less++] = a[great]; 1751 a[great--] = ak; 1752 } else { // pivot1 <= a[great] <= pivot2 1753 a[k] = a[great]; 1754 a[great--] = ak; 1755 } 1756 } 1757 } 1758 } else { // Pivots are equal 1759 /* 1760 * Partition degenerates to the traditional 3-way, 1761 * or "Dutch National Flag", partition: 1762 * 1763 * left part center part right part 1764 * +----------------------------------------------+ 1765 * | < pivot | == pivot | ? | > pivot | 1766 * +----------------------------------------------+ 1767 * ^ ^ ^ 1768 * | | | 1769 * less k great 1770 * 1771 * Invariants: 1772 * 1773 * all in (left, less) < pivot 1774 * all in [less, k) == pivot 1775 * all in (great, right) > pivot 1776 * 1777 * Pointer k is the first index of ?-part 1778 */ 1779 for (int k = less; k <= great; k++) { 1780 float ak = a[k]; 1781 if (ak == pivot1) { 1782 continue; 1783 } 1784 if (ak < pivot1) { // Move a[k] to left part 1785 if (k != less) { 1786 a[k] = a[less]; 1787 a[less] = ak; 1788 } 1789 less++; 1790 } else { // (a[k] > pivot1) - Move a[k] to right part 1791 /* 1792 * We know that pivot1 == a[e3] == pivot2. Thus, we know 1793 * that great will still be >= k when the following loop 1794 * terminates, even though we don't test for it explicitly. 1795 * In other words, a[e3] acts as a sentinel for great. 1796 */ 1797 while (a[great] > pivot1) { 1798 great--; 1799 } 1800 if (a[great] < pivot1) { 1801 a[k] = a[less]; 1802 a[less++] = a[great]; 1803 a[great--] = ak; 1804 } else { // a[great] == pivot1 1805 a[k] = pivot1; 1806 a[great--] = ak; 1807 } 1808 } 1809 } 1810 } 1811 1812 // Swap pivots into their final positions 1813 a[left] = a[less - 1]; a[less - 1] = pivot1; 1814 a[right] = a[great + 1]; a[great + 1] = pivot2; 1815 1816 // Sort left and right parts recursively, excluding known pivot values 1817 doSort(a, left, less - 2); 1818 doSort(a, great + 2, right); 1819 1820 /* 1821 * If pivot1 == pivot2, all elements from center 1822 * part are equal and, therefore, already sorted 1823 */ 1824 if (!pivotsDiffer) { 1825 return; 1826 } 1827 1828 /* 1829 * If center part is too large (comprises > 2/3 of the array), 1830 * swap internal pivot values to ends 1831 */ 1832 if (less < e1 && great > e5) { 1833 while (a[less] == pivot1) { 1834 less++; 1835 } 1836 while (a[great] == pivot2) { 1837 great--; 1838 } 1839 1840 /* 1841 * Partitioning: 1842 * 1843 * left part center part right part 1844 * +----------------------------------------------------------+ 1845 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 1846 * +----------------------------------------------------------+ 1847 * ^ ^ ^ 1848 * | | | 1849 * less k great 1850 * 1851 * Invariants: 1852 * 1853 * all in (*, less) == pivot1 1854 * pivot1 < all in [less, k) < pivot2 1855 * all in (great, *) == pivot2 1856 * 1857 * Pointer k is the first index of ?-part 1858 */ 1859 outer: 1860 for (int k = less; k <= great; k++) { 1861 float ak = a[k]; 1862 if (ak == pivot2) { // Move a[k] to right part 1863 while (a[great] == pivot2) { 1864 if (great-- == k) { 1865 break outer; 1866 } 1867 } 1868 if (a[great] == pivot1) { 1869 a[k] = a[less]; 1870 a[less++] = pivot1; 1871 } else { // pivot1 < a[great] < pivot2 1872 a[k] = a[great]; 1873 } 1874 a[great--] = pivot2; 1875 } else if (ak == pivot1) { // Move a[k] to left part 1876 a[k] = a[less]; 1877 a[less++] = pivot1; 1878 } 1879 } 1880 } 1881 1882 // Sort center part recursively, excluding known pivot values 1883 doSort(a, less, great); 1884 } 1885 1886 /** 1887 * Sorts the specified array into ascending numerical order. 1888 * 1889 * <p>The {@code <} relation does not provide a total order on all double 1890 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 1891 * value compares neither less than, greater than, nor equal to any value, 1892 * even itself. This method uses the total order imposed by the method 1893 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 1894 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 1895 * other value and all {@code Double.NaN} values are considered equal. 1896 * 1897 * @param a the array to be sorted 1898 */ 1899 public static void sort(double[] a) { 1900 sortNegZeroAndNaN(a, 0, a.length - 1); 1901 } 1902 1903 /** 1904 * Sorts the specified range of the array into ascending order. The range 1905 * to be sorted extends from the index {@code fromIndex}, inclusive, to 1906 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 1907 * the range to be sorted is empty (and the call is a no-op). 1908 * 1909 * <p>The {@code <} relation does not provide a total order on all double 1910 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 1911 * value compares neither less than, greater than, nor equal to any value, 1912 * even itself. This method uses the total order imposed by the method 1913 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 1914 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 1915 * other value and all {@code Double.NaN} values are considered equal. 1916 * 1917 * @param a the array to be sorted 1918 * @param fromIndex the index of the first element, inclusive, to be sorted 1919 * @param toIndex the index of the last element, exclusive, to be sorted 1920 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1921 * @throws ArrayIndexOutOfBoundsException 1922 * if {@code fromIndex < 0} or {@code toIndex > a.length} 1923 */ 1924 public static void sort(double[] a, int fromIndex, int toIndex) { 1925 rangeCheck(a.length, fromIndex, toIndex); 1926 sortNegZeroAndNaN(a, fromIndex, toIndex - 1); 1927 } 1928 1929 /** 1930 * Sorts the specified range of the array into ascending order. The 1931 * sort is done in three phases to avoid expensive comparisons in the 1932 * inner loop. The comparisons would be expensive due to anomalies 1933 * associated with negative zero {@code -0.0d} and {@code Double.NaN}. 1934 * 1935 * @param a the array to be sorted 1936 * @param left the index of the first element, inclusive, to be sorted 1937 * @param right the index of the last element, inclusive, to be sorted 1938 */ 1939 private static void sortNegZeroAndNaN(double[] a, int left, int right) { 1940 /* 1941 * Phase 1: Count negative zeros and move NaNs to end of array 1942 */ 1943 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d); 1944 int numNegativeZeros = 0; 1945 int n = right; 1946 1947 for (int k = left; k <= n; k++) { 1948 double ak = a[k]; 1949 if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) { 1950 a[k] = 0.0d; 1951 numNegativeZeros++; 1952 } else if (ak != ak) { // i.e., ak is NaN 1953 a[k--] = a[n]; 1954 a[n--] = Double.NaN; 1955 } 1956 } 1957 1958 /* 1959 * Phase 2: Sort everything except NaNs (which are already in place) 1960 */ 1961 doSort(a, left, n); 1962 1963 /* 1964 * Phase 3: Turn positive zeros back into negative zeros as appropriate 1965 */ 1966 if (numNegativeZeros == 0) { 1967 return; 1968 } 1969 1970 // Find first zero element 1971 int zeroIndex = findAnyZero(a, left, n); 1972 1973 for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) { 1974 zeroIndex = i; 1975 } 1976 1977 // Turn the right number of positive zeros back into negative zeros 1978 for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) { 1979 a[i] = -0.0d; 1980 } 1981 } 1982 1983 /** 1984 * Returns the index of some zero element in the specified range via 1985 * binary search. The range is assumed to be sorted, and must contain 1986 * at least one zero. 1987 * 1988 * @param a the array to be searched 1989 * @param low the index of the first element, inclusive, to be searched 1990 * @param high the index of the last element, inclusive, to be searched 1991 */ 1992 private static int findAnyZero(double[] a, int low, int high) { 1993 while (true) { 1994 int middle = (low + high) >>> 1; 1995 double middleValue = a[middle]; 1996 1997 if (middleValue < 0.0d) { 1998 low = middle + 1; 1999 } else if (middleValue > 0.0d) { 2000 high = middle - 1; 2001 } else { // middleValue == 0.0d 2002 return middle; 2003 } 2004 } 2005 } 2006 2007 /** 2008 * Sorts the specified range of the array into ascending order. This 2009 * method differs from the public {@code sort} method in three ways: 2010 * {@code right} index is inclusive, it does no range checking on 2011 * {@code left} or {@code right}, and it does not handle negative 2012 * zeros or NaNs in the array. 2013 * 2014 * @param a the array to be sorted, which must not contain -0.0d and NaN 2015 * @param left the index of the first element, inclusive, to be sorted 2016 * @param right the index of the last element, inclusive, to be sorted 2017 */ 2018 private static void doSort(double[] a, int left, int right) { 2019 // Use insertion sort on tiny arrays 2020 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 2021 for (int i = left + 1; i <= right; i++) { 2022 double ai = a[i]; 2023 int j; 2024 for (j = i - 1; j >= left && ai < a[j]; j--) { 2025 a[j + 1] = a[j]; 2026 } 2027 a[j + 1] = ai; 2028 } 2029 } else { // Use Dual-Pivot Quicksort on large arrays 2030 dualPivotQuicksort(a, left, right); 2031 } 2032 } 2033 2034 /** 2035 * Sorts the specified range of the array into ascending order by the 2036 * Dual-Pivot Quicksort algorithm. 2037 * 2038 * @param a the array to be sorted 2039 * @param left the index of the first element, inclusive, to be sorted 2040 * @param right the index of the last element, inclusive, to be sorted 2041 */ 2042 private static void dualPivotQuicksort(double[] a, int left, int right) { 2043 // Compute indices of five evenly spaced elements 2044 int sixth = (right - left + 1) / 6; 2045 int e1 = left + sixth; 2046 int e5 = right - sixth; 2047 int e3 = (left + right) >>> 1; // The midpoint 2048 int e4 = e3 + sixth; 2049 int e2 = e3 - sixth; 2050 2051 // Sort these elements using a 5-element sorting network 2052 double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5]; 2053 2054 if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; } 2055 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; } 2056 if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; } 2057 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; } 2058 if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; } 2059 if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; } 2060 if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; } 2061 if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; } 2062 if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; } 2063 2064 a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; 2065 2066 /* 2067 * Use the second and fourth of the five sorted elements as pivots. 2068 * These values are inexpensive approximations of the first and 2069 * second terciles of the array. Note that pivot1 <= pivot2. 2070 * 2071 * The pivots are stored in local variables, and the first and 2072 * the last of the elements to be sorted are moved to the locations 2073 * formerly occupied by the pivots. When partitioning is complete, 2074 * the pivots are swapped back into their final positions, and 2075 * excluded from subsequent sorting. 2076 */ 2077 double pivot1 = ae2; a[e2] = a[left]; 2078 double pivot2 = ae4; a[e4] = a[right]; 2079 2080 // Pointers 2081 int less = left + 1; // The index of first element of center part 2082 int great = right - 1; // The index before first element of right part 2083 2084 boolean pivotsDiffer = (pivot1 != pivot2); 2085 2086 if (pivotsDiffer) { 2087 /* 2088 * Partitioning: 2089 * 2090 * left part center part right part 2091 * +------------------------------------------------------------+ 2092 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2093 * +------------------------------------------------------------+ 2094 * ^ ^ ^ 2095 * | | | 2096 * less k great 2097 * 2098 * Invariants: 2099 * 2100 * all in (left, less) < pivot1 2101 * pivot1 <= all in [less, k) <= pivot2 2102 * all in (great, right) > pivot2 2103 * 2104 * Pointer k is the first index of ?-part 2105 */ 2106 outer: 2107 for (int k = less; k <= great; k++) { 2108 double ak = a[k]; 2109 if (ak < pivot1) { // Move a[k] to left part 2110 if (k != less) { 2111 a[k] = a[less]; 2112 a[less] = ak; 2113 } 2114 less++; 2115 } else if (ak > pivot2) { // Move a[k] to right part 2116 while (a[great] > pivot2) { 2117 if (great-- == k) { 2118 break outer; 2119 } 2120 } 2121 if (a[great] < pivot1) { 2122 a[k] = a[less]; 2123 a[less++] = a[great]; 2124 a[great--] = ak; 2125 } else { // pivot1 <= a[great] <= pivot2 2126 a[k] = a[great]; 2127 a[great--] = ak; 2128 } 2129 } 2130 } 2131 } else { // Pivots are equal 2132 /* 2133 * Partition degenerates to the traditional 3-way, 2134 * or "Dutch National Flag", partition: 2135 * 2136 * left part center part right part 2137 * +----------------------------------------------+ 2138 * | < pivot | == pivot | ? | > pivot | 2139 * +----------------------------------------------+ 2140 * ^ ^ ^ 2141 * | | | 2142 * less k great 2143 * 2144 * Invariants: 2145 * 2146 * all in (left, less) < pivot 2147 * all in [less, k) == pivot 2148 * all in (great, right) > pivot 2149 * 2150 * Pointer k is the first index of ?-part 2151 */ 2152 for (int k = less; k <= great; k++) { 2153 double ak = a[k]; 2154 if (ak == pivot1) { 2155 continue; 2156 } 2157 if (ak < pivot1) { // Move a[k] to left part 2158 if (k != less) { 2159 a[k] = a[less]; 2160 a[less] = ak; 2161 } 2162 less++; 2163 } else { // (a[k] > pivot1) - Move a[k] to right part 2164 /* 2165 * We know that pivot1 == a[e3] == pivot2. Thus, we know 2166 * that great will still be >= k when the following loop 2167 * terminates, even though we don't test for it explicitly. 2168 * In other words, a[e3] acts as a sentinel for great. 2169 */ 2170 while (a[great] > pivot1) { 2171 great--; 2172 } 2173 if (a[great] < pivot1) { 2174 a[k] = a[less]; 2175 a[less++] = a[great]; 2176 a[great--] = ak; 2177 } else { // a[great] == pivot1 2178 a[k] = pivot1; 2179 a[great--] = ak; 2180 } 2181 } 2182 } 2183 } 2184 2185 // Swap pivots into their final positions 2186 a[left] = a[less - 1]; a[less - 1] = pivot1; 2187 a[right] = a[great + 1]; a[great + 1] = pivot2; 2188 2189 // Sort left and right parts recursively, excluding known pivot values 2190 doSort(a, left, less - 2); 2191 doSort(a, great + 2, right); 2192 2193 /* 2194 * If pivot1 == pivot2, all elements from center 2195 * part are equal and, therefore, already sorted 2196 */ 2197 if (!pivotsDiffer) { 2198 return; 2199 } 2200 2201 /* 2202 * If center part is too large (comprises > 2/3 of the array), 2203 * swap internal pivot values to ends 2204 */ 2205 if (less < e1 && great > e5) { 2206 while (a[less] == pivot1) { 2207 less++; 2208 } 2209 while (a[great] == pivot2) { 2210 great--; 2211 } 2212 2213 /* 2214 * Partitioning: 2215 * 2216 * left part center part right part 2217 * +----------------------------------------------------------+ 2218 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2219 * +----------------------------------------------------------+ 2220 * ^ ^ ^ 2221 * | | | 2222 * less k great 2223 * 2224 * Invariants: 2225 * 2226 * all in (*, less) == pivot1 2227 * pivot1 < all in [less, k) < pivot2 2228 * all in (great, *) == pivot2 2229 * 2230 * Pointer k is the first index of ?-part 2231 */ 2232 outer: 2233 for (int k = less; k <= great; k++) { 2234 double ak = a[k]; 2235 if (ak == pivot2) { // Move a[k] to right part 2236 while (a[great] == pivot2) { 2237 if (great-- == k) { 2238 break outer; 2239 } 2240 } 2241 if (a[great] == pivot1) { 2242 a[k] = a[less]; 2243 a[less++] = pivot1; 2244 } else { // pivot1 < a[great] < pivot2 2245 a[k] = a[great]; 2246 } 2247 a[great--] = pivot2; 2248 } else if (ak == pivot1) { // Move a[k] to left part 2249 a[k] = a[less]; 2250 a[less++] = pivot1; 2251 } 2252 } 2253 } 2254 2255 // Sort center part recursively, excluding known pivot values 2256 doSort(a, less, great); 2257 } 2258 2259 /** 2260 * Checks that {@code fromIndex} and {@code toIndex} are in 2261 * the range and throws an appropriate exception, if they aren't. 2262 */ 2263 private static void rangeCheck(int length, int fromIndex, int toIndex) { 2264 if (fromIndex > toIndex) { 2265 throw new IllegalArgumentException( 2266 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); 2267 } 2268 if (fromIndex < 0) { 2269 throw new ArrayIndexOutOfBoundsException(fromIndex); 2270 } 2271 if (toIndex > length) { 2272 throw new ArrayIndexOutOfBoundsException(toIndex); 2273 } 2274 } 2275 }