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