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