1/* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package java.util; 18 19/** 20 * A stable, adaptive, iterative mergesort that requires far fewer than 21 * n lg(n) comparisons when running on partially sorted arrays, while 22 * offering performance comparable to a traditional mergesort when run 23 * on random arrays. Like all proper mergesorts, this sort is stable and 24 * runs O(n log n) time (worst case). In the worst case, this sort requires 25 * temporary storage space for n/2 object references; in the best case, 26 * it requires only a small constant amount of space. 27 * 28 * This implementation was adapted from Tim Peters's list sort for 29 * Python, which is described in detail here: 30 * 31 * http://svn.python.org/projects/python/trunk/Objects/listsort.txt 32 * 33 * Tim's C code may be found here: 34 * 35 * http://svn.python.org/projects/python/trunk/Objects/listobject.c 36 * 37 * The underlying techniques are described in this paper (and may have 38 * even earlier origins): 39 * 40 * "Optimistic Sorting and Information Theoretic Complexity" 41 * Peter McIlroy 42 * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 43 * pp 467-474, Austin, Texas, 25-27 January 1993. 44 * 45 * While the API to this class consists solely of static methods, it is 46 * (privately) instantiable; a TimSort instance holds the state of an ongoing 47 * sort, assuming the input array is large enough to warrant the full-blown 48 * TimSort. Small arrays are sorted in place, using a binary insertion sort. 49 */ 50class TimSort<T> { 51 /** 52 * This is the minimum sized sequence that will be merged. Shorter 53 * sequences will be lengthened by calling binarySort. If the entire 54 * array is less than this length, no merges will be performed. 55 * 56 * This constant should be a power of two. It was 64 in Tim Peter's C 57 * implementation, but 32 was empirically determined to work better in 58 * this implementation. In the unlikely event that you set this constant 59 * to be a number that's not a power of two, you'll need to change the 60 * {@link #minRunLength} computation. 61 * 62 * If you decrease this constant, you must change the stackLen 63 * computation in the TimSort constructor, or you risk an 64 * ArrayOutOfBounds exception. See listsort.txt for a discussion 65 * of the minimum stack length required as a function of the length 66 * of the array being sorted and the minimum merge sequence length. 67 */ 68 private static final int MIN_MERGE = 32; 69 70 /** 71 * The array being sorted. 72 */ 73 private final T[] a; 74 75 /** 76 * The comparator for this sort. 77 */ 78 private final Comparator<? super T> c; 79 80 /** 81 * When we get into galloping mode, we stay there until both runs win less 82 * often than MIN_GALLOP consecutive times. 83 */ 84 private static final int MIN_GALLOP = 7; 85 86 /** 87 * This controls when we get *into* galloping mode. It is initialized 88 * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for 89 * random data, and lower for highly structured data. 90 */ 91 private int minGallop = MIN_GALLOP; 92 93 /** 94 * Maximum initial size of tmp array, which is used for merging. The array 95 * can grow to accommodate demand. 96 * 97 * Unlike Tim's original C version, we do not allocate this much storage 98 * when sorting smaller arrays. This change was required for performance. 99 */ 100 private static final int INITIAL_TMP_STORAGE_LENGTH = 256; 101 102 /** 103 * Temp storage for merges. 104 */ 105 private T[] tmp; // Actual runtime type will be Object[], regardless of T 106 107 /** 108 * A stack of pending runs yet to be merged. Run i starts at 109 * address base[i] and extends for len[i] elements. It's always 110 * true (so long as the indices are in bounds) that: 111 * 112 * runBase[i] + runLen[i] == runBase[i + 1] 113 * 114 * so we could cut the storage for this, but it's a minor amount, 115 * and keeping all the info explicit simplifies the code. 116 */ 117 private int stackSize = 0; // Number of pending runs on stack 118 private final int[] runBase; 119 private final int[] runLen; 120 121 /** 122 * Asserts have been placed in if-statements for performace. To enable them, 123 * set this field to true and enable them in VM with a command line flag. 124 * If you modify this class, please do test the asserts! 125 */ 126 private static final boolean DEBUG = false; 127 128 /** 129 * Creates a TimSort instance to maintain the state of an ongoing sort. 130 * 131 * @param a the array to be sorted 132 * @param c the comparator to determine the order of the sort 133 */ 134 private TimSort(T[] a, Comparator<? super T> c) { 135 this.a = a; 136 this.c = c; 137 138 // Allocate temp storage (which may be increased later if necessary) 139 int len = a.length; 140 @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) 141 T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ? 142 len >>> 1 : INITIAL_TMP_STORAGE_LENGTH]; 143 tmp = newArray; 144 145 /* 146 * Allocate runs-to-be-merged stack (which cannot be expanded). The 147 * stack length requirements are described in listsort.txt. The C 148 * version always uses the same stack length (85), but this was 149 * measured to be too expensive when sorting "mid-sized" arrays (e.g., 150 * 100 elements) in Java. Therefore, we use smaller (but sufficiently 151 * large) stack lengths for smaller arrays. The "magic numbers" in the 152 * computation below must be changed if MIN_MERGE is decreased. See 153 * the MIN_MERGE declaration above for more information. 154 */ 155 int stackLen = (len < 120 ? 5 : 156 len < 1542 ? 10 : 157 len < 119151 ? 19 : 40); 158 runBase = new int[stackLen]; 159 runLen = new int[stackLen]; 160 } 161 162 /* 163 * The next two methods (which are package private and static) constitute 164 * the entire API of this class. Each of these methods obeys the contract 165 * of the public method with the same signature in java.util.Arrays. 166 */ 167 168 static <T> void sort(T[] a, Comparator<? super T> c) { 169 sort(a, 0, a.length, c); 170 } 171 172 static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) { 173 if (c == null) { 174 Arrays.sort(a, lo, hi); 175 return; 176 } 177 178 Arrays.checkStartAndEnd(a.length, lo, hi); 179 int nRemaining = hi - lo; 180 if (nRemaining < 2) 181 return; // Arrays of size 0 and 1 are always sorted 182 183 // If array is small, do a "mini-TimSort" with no merges 184 if (nRemaining < MIN_MERGE) { 185 int initRunLen = countRunAndMakeAscending(a, lo, hi, c); 186 binarySort(a, lo, hi, lo + initRunLen, c); 187 return; 188 } 189 190 /** 191 * March over the array once, left to right, finding natural runs, 192 * extending short natural runs to minRun elements, and merging runs 193 * to maintain stack invariant. 194 */ 195 TimSort<T> ts = new TimSort<T>(a, c); 196 int minRun = minRunLength(nRemaining); 197 do { 198 // Identify next run 199 int runLen = countRunAndMakeAscending(a, lo, hi, c); 200 201 // If run is short, extend to min(minRun, nRemaining) 202 if (runLen < minRun) { 203 int force = nRemaining <= minRun ? nRemaining : minRun; 204 binarySort(a, lo, lo + force, lo + runLen, c); 205 runLen = force; 206 } 207 208 // Push run onto pending-run stack, and maybe merge 209 ts.pushRun(lo, runLen); 210 ts.mergeCollapse(); 211 212 // Advance to find next run 213 lo += runLen; 214 nRemaining -= runLen; 215 } while (nRemaining != 0); 216 217 // Merge all remaining runs to complete sort 218 if (DEBUG) assert lo == hi; 219 ts.mergeForceCollapse(); 220 if (DEBUG) assert ts.stackSize == 1; 221 } 222 223 /** 224 * Sorts the specified portion of the specified array using a binary 225 * insertion sort. This is the best method for sorting small numbers 226 * of elements. It requires O(n log n) compares, but O(n^2) data 227 * movement (worst case). 228 * 229 * If the initial part of the specified range is already sorted, 230 * this method can take advantage of it: the method assumes that the 231 * elements from index {@code lo}, inclusive, to {@code start}, 232 * exclusive are already sorted. 233 * 234 * @param a the array in which a range is to be sorted 235 * @param lo the index of the first element in the range to be sorted 236 * @param hi the index after the last element in the range to be sorted 237 * @param start the index of the first element in the range that is 238 * not already known to be sorted (@code lo <= start <= hi} 239 * @param c comparator to used for the sort 240 */ 241 @SuppressWarnings("fallthrough") 242 private static <T> void binarySort(T[] a, int lo, int hi, int start, 243 Comparator<? super T> c) { 244 if (DEBUG) assert lo <= start && start <= hi; 245 if (start == lo) 246 start++; 247 for ( ; start < hi; start++) { 248 T pivot = a[start]; 249 250 // Set left (and right) to the index where a[start] (pivot) belongs 251 int left = lo; 252 int right = start; 253 if (DEBUG) assert left <= right; 254 /* 255 * Invariants: 256 * pivot >= all in [lo, left). 257 * pivot < all in [right, start). 258 */ 259 while (left < right) { 260 int mid = (left + right) >>> 1; 261 if (c.compare(pivot, a[mid]) < 0) 262 right = mid; 263 else 264 left = mid + 1; 265 } 266 if (DEBUG) assert left == right; 267 268 /* 269 * The invariants still hold: pivot >= all in [lo, left) and 270 * pivot < all in [left, start), so pivot belongs at left. Note 271 * that if there are elements equal to pivot, left points to the 272 * first slot after them -- that's why this sort is stable. 273 * Slide elements over to make room for pivot. 274 */ 275 int n = start - left; // The number of elements to move 276 // Switch is just an optimization for arraycopy in default case 277 switch(n) { 278 case 2: a[left + 2] = a[left + 1]; 279 case 1: a[left + 1] = a[left]; 280 break; 281 default: System.arraycopy(a, left, a, left + 1, n); 282 } 283 a[left] = pivot; 284 } 285 } 286 287 /** 288 * Returns the length of the run beginning at the specified position in 289 * the specified array and reverses the run if it is descending (ensuring 290 * that the run will always be ascending when the method returns). 291 * 292 * A run is the longest ascending sequence with: 293 * 294 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 295 * 296 * or the longest descending sequence with: 297 * 298 * a[lo] > a[lo + 1] > a[lo + 2] > ... 299 * 300 * For its intended use in a stable mergesort, the strictness of the 301 * definition of "descending" is needed so that the call can safely 302 * reverse a descending sequence without violating stability. 303 * 304 * @param a the array in which a run is to be counted and possibly reversed 305 * @param lo index of the first element in the run 306 * @param hi index after the last element that may be contained in the run. 307 It is required that @code{lo < hi}. 308 * @param c the comparator to used for the sort 309 * @return the length of the run beginning at the specified position in 310 * the specified array 311 */ 312 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 313 Comparator<? super T> c) { 314 if (DEBUG) assert lo < hi; 315 int runHi = lo + 1; 316 if (runHi == hi) 317 return 1; 318 319 // Find end of run, and reverse range if descending 320 if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 321 while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) 322 runHi++; 323 reverseRange(a, lo, runHi); 324 } else { // Ascending 325 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 326 runHi++; 327 } 328 329 return runHi - lo; 330 } 331 332 /** 333 * Reverse the specified range of the specified array. 334 * 335 * @param a the array in which a range is to be reversed 336 * @param lo the index of the first element in the range to be reversed 337 * @param hi the index after the last element in the range to be reversed 338 */ 339 private static void reverseRange(Object[] a, int lo, int hi) { 340 hi--; 341 while (lo < hi) { 342 Object t = a[lo]; 343 a[lo++] = a[hi]; 344 a[hi--] = t; 345 } 346 } 347 348 /** 349 * Returns the minimum acceptable run length for an array of the specified 350 * length. Natural runs shorter than this will be extended with 351 * {@link #binarySort}. 352 * 353 * Roughly speaking, the computation is: 354 * 355 * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). 356 * Else if n is an exact power of 2, return MIN_MERGE/2. 357 * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k 358 * is close to, but strictly less than, an exact power of 2. 359 * 360 * For the rationale, see listsort.txt. 361 * 362 * @param n the length of the array to be sorted 363 * @return the length of the minimum run to be merged 364 */ 365 private static int minRunLength(int n) { 366 if (DEBUG) assert n >= 0; 367 int r = 0; // Becomes 1 if any 1 bits are shifted off 368 while (n >= MIN_MERGE) { 369 r |= (n & 1); 370 n >>= 1; 371 } 372 return n + r; 373 } 374 375 /** 376 * Pushes the specified run onto the pending-run stack. 377 * 378 * @param runBase index of the first element in the run 379 * @param runLen the number of elements in the run 380 */ 381 private void pushRun(int runBase, int runLen) { 382 this.runBase[stackSize] = runBase; 383 this.runLen[stackSize] = runLen; 384 stackSize++; 385 } 386 387 /** 388 * Examines the stack of runs waiting to be merged and merges adjacent runs 389 * until the stack invariants are reestablished: 390 * 391 * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 392 * 2. runLen[i - 2] > runLen[i - 1] 393 * 394 * This method is called each time a new run is pushed onto the stack, 395 * so the invariants are guaranteed to hold for i < stackSize upon 396 * entry to the method. 397 */ 398 private void mergeCollapse() { 399 while (stackSize > 1) { 400 int n = stackSize - 2; 401 if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { 402 if (runLen[n - 1] < runLen[n + 1]) 403 n--; 404 mergeAt(n); 405 } else if (runLen[n] <= runLen[n + 1]) { 406 mergeAt(n); 407 } else { 408 break; // Invariant is established 409 } 410 } 411 } 412 413 /** 414 * Merges all runs on the stack until only one remains. This method is 415 * called once, to complete the sort. 416 */ 417 private void mergeForceCollapse() { 418 while (stackSize > 1) { 419 int n = stackSize - 2; 420 if (n > 0 && runLen[n - 1] < runLen[n + 1]) 421 n--; 422 mergeAt(n); 423 } 424 } 425 426 /** 427 * Merges the two runs at stack indices i and i+1. Run i must be 428 * the penultimate or antepenultimate run on the stack. In other words, 429 * i must be equal to stackSize-2 or stackSize-3. 430 * 431 * @param i stack index of the first of the two runs to merge 432 */ 433 private void mergeAt(int i) { 434 if (DEBUG) assert stackSize >= 2; 435 if (DEBUG) assert i >= 0; 436 if (DEBUG) assert i == stackSize - 2 || i == stackSize - 3; 437 438 int base1 = runBase[i]; 439 int len1 = runLen[i]; 440 int base2 = runBase[i + 1]; 441 int len2 = runLen[i + 1]; 442 if (DEBUG) assert len1 > 0 && len2 > 0; 443 if (DEBUG) assert base1 + len1 == base2; 444 445 /* 446 * Record the length of the combined runs; if i is the 3rd-last 447 * run now, also slide over the last run (which isn't involved 448 * in this merge). The current run (i+1) goes away in any case. 449 */ 450 runLen[i] = len1 + len2; 451 if (i == stackSize - 3) { 452 runBase[i + 1] = runBase[i + 2]; 453 runLen[i + 1] = runLen[i + 2]; 454 } 455 stackSize--; 456 457 /* 458 * Find where the first element of run2 goes in run1. Prior elements 459 * in run1 can be ignored (because they're already in place). 460 */ 461 int k = gallopRight(a[base2], a, base1, len1, 0, c); 462 if (DEBUG) assert k >= 0; 463 base1 += k; 464 len1 -= k; 465 if (len1 == 0) 466 return; 467 468 /* 469 * Find where the last element of run1 goes in run2. Subsequent elements 470 * in run2 can be ignored (because they're already in place). 471 */ 472 len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c); 473 if (DEBUG) assert len2 >= 0; 474 if (len2 == 0) 475 return; 476 477 // Merge remaining runs, using tmp array with min(len1, len2) elements 478 if (len1 <= len2) 479 mergeLo(base1, len1, base2, len2); 480 else 481 mergeHi(base1, len1, base2, len2); 482 } 483 484 /** 485 * Locates the position at which to insert the specified key into the 486 * specified sorted range; if the range contains an element equal to key, 487 * returns the index of the leftmost equal element. 488 * 489 * @param key the key whose insertion point to search for 490 * @param a the array in which to search 491 * @param base the index of the first element in the range 492 * @param len the length of the range; must be > 0 493 * @param hint the index at which to begin the search, 0 <= hint < n. 494 * The closer hint is to the result, the faster this method will run. 495 * @param c the comparator used to order the range, and to search 496 * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], 497 * pretending that a[b - 1] is minus infinity and a[b + n] is infinity. 498 * In other words, key belongs at index b + k; or in other words, 499 * the first k elements of a should precede key, and the last n - k 500 * should follow it. 501 */ 502 private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, 503 Comparator<? super T> c) { 504 if (DEBUG) assert len > 0 && hint >= 0 && hint < len; 505 int lastOfs = 0; 506 int ofs = 1; 507 if (c.compare(key, a[base + hint]) > 0) { 508 // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs] 509 int maxOfs = len - hint; 510 while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) { 511 lastOfs = ofs; 512 ofs = (ofs * 2) + 1; 513 if (ofs <= 0) // int overflow 514 ofs = maxOfs; 515 } 516 if (ofs > maxOfs) 517 ofs = maxOfs; 518 519 // Make offsets relative to base 520 lastOfs += hint; 521 ofs += hint; 522 } else { // key <= a[base + hint] 523 // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs] 524 final int maxOfs = hint + 1; 525 while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) { 526 lastOfs = ofs; 527 ofs = (ofs * 2) + 1; 528 if (ofs <= 0) // int overflow 529 ofs = maxOfs; 530 } 531 if (ofs > maxOfs) 532 ofs = maxOfs; 533 534 // Make offsets relative to base 535 int tmp = lastOfs; 536 lastOfs = hint - ofs; 537 ofs = hint - tmp; 538 } 539 if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 540 541 /* 542 * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere 543 * to the right of lastOfs but no farther right than ofs. Do a binary 544 * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs]. 545 */ 546 lastOfs++; 547 while (lastOfs < ofs) { 548 int m = lastOfs + ((ofs - lastOfs) >>> 1); 549 550 if (c.compare(key, a[base + m]) > 0) 551 lastOfs = m + 1; // a[base + m] < key 552 else 553 ofs = m; // key <= a[base + m] 554 } 555 if (DEBUG) assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs] 556 return ofs; 557 } 558 559 /** 560 * Like gallopLeft, except that if the range contains an element equal to 561 * key, gallopRight returns the index after the rightmost equal element. 562 * 563 * @param key the key whose insertion point to search for 564 * @param a the array in which to search 565 * @param base the index of the first element in the range 566 * @param len the length of the range; must be > 0 567 * @param hint the index at which to begin the search, 0 <= hint < n. 568 * The closer hint is to the result, the faster this method will run. 569 * @param c the comparator used to order the range, and to search 570 * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] 571 */ 572 private static <T> int gallopRight(T key, T[] a, int base, int len, 573 int hint, Comparator<? super T> c) { 574 if (DEBUG) assert len > 0 && hint >= 0 && hint < len; 575 576 int ofs = 1; 577 int lastOfs = 0; 578 if (c.compare(key, a[base + hint]) < 0) { 579 // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs] 580 int maxOfs = hint + 1; 581 while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) { 582 lastOfs = ofs; 583 ofs = (ofs * 2) + 1; 584 if (ofs <= 0) // int overflow 585 ofs = maxOfs; 586 } 587 if (ofs > maxOfs) 588 ofs = maxOfs; 589 590 // Make offsets relative to b 591 int tmp = lastOfs; 592 lastOfs = hint - ofs; 593 ofs = hint - tmp; 594 } else { // a[b + hint] <= key 595 // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs] 596 int maxOfs = len - hint; 597 while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) { 598 lastOfs = ofs; 599 ofs = (ofs * 2) + 1; 600 if (ofs <= 0) // int overflow 601 ofs = maxOfs; 602 } 603 if (ofs > maxOfs) 604 ofs = maxOfs; 605 606 // Make offsets relative to b 607 lastOfs += hint; 608 ofs += hint; 609 } 610 if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 611 612 /* 613 * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to 614 * the right of lastOfs but no farther right than ofs. Do a binary 615 * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs]. 616 */ 617 lastOfs++; 618 while (lastOfs < ofs) { 619 int m = lastOfs + ((ofs - lastOfs) >>> 1); 620 621 if (c.compare(key, a[base + m]) < 0) 622 ofs = m; // key < a[b + m] 623 else 624 lastOfs = m + 1; // a[b + m] <= key 625 } 626 if (DEBUG) assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs] 627 return ofs; 628 } 629 630 /** 631 * Merges two adjacent runs in place, in a stable fashion. The first 632 * element of the first run must be greater than the first element of the 633 * second run (a[base1] > a[base2]), and the last element of the first run 634 * (a[base1 + len1-1]) must be greater than all elements of the second run. 635 * 636 * For performance, this method should be called only when len1 <= len2; 637 * its twin, mergeHi should be called if len1 >= len2. (Either method 638 * may be called if len1 == len2.) 639 * 640 * @param base1 index of first element in first run to be merged 641 * @param len1 length of first run to be merged (must be > 0) 642 * @param base2 index of first element in second run to be merged 643 * (must be aBase + aLen) 644 * @param len2 length of second run to be merged (must be > 0) 645 */ 646 private void mergeLo(int base1, int len1, int base2, int len2) { 647 if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 648 649 // Copy first run into temp array 650 T[] a = this.a; // For performance 651 T[] tmp = ensureCapacity(len1); 652 System.arraycopy(a, base1, tmp, 0, len1); 653 654 int cursor1 = 0; // Indexes into tmp array 655 int cursor2 = base2; // Indexes int a 656 int dest = base1; // Indexes int a 657 658 // Move first element of second run and deal with degenerate cases 659 a[dest++] = a[cursor2++]; 660 if (--len2 == 0) { 661 System.arraycopy(tmp, cursor1, a, dest, len1); 662 return; 663 } 664 if (len1 == 1) { 665 System.arraycopy(a, cursor2, a, dest, len2); 666 a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge 667 return; 668 } 669 670 Comparator<? super T> c = this.c; // Use local variable for performance 671 int minGallop = this.minGallop; // " " " " " 672 outer: 673 while (true) { 674 int count1 = 0; // Number of times in a row that first run won 675 int count2 = 0; // Number of times in a row that second run won 676 677 /* 678 * Do the straightforward thing until (if ever) one run starts 679 * winning consistently. 680 */ 681 do { 682 if (DEBUG) assert len1 > 1 && len2 > 0; 683 if (c.compare(a[cursor2], tmp[cursor1]) < 0) { 684 a[dest++] = a[cursor2++]; 685 count2++; 686 count1 = 0; 687 if (--len2 == 0) 688 break outer; 689 } else { 690 a[dest++] = tmp[cursor1++]; 691 count1++; 692 count2 = 0; 693 if (--len1 == 1) 694 break outer; 695 } 696 } while ((count1 | count2) < minGallop); 697 698 /* 699 * One run is winning so consistently that galloping may be a 700 * huge win. So try that, and continue galloping until (if ever) 701 * neither run appears to be winning consistently anymore. 702 */ 703 do { 704 if (DEBUG) assert len1 > 1 && len2 > 0; 705 count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c); 706 if (count1 != 0) { 707 System.arraycopy(tmp, cursor1, a, dest, count1); 708 dest += count1; 709 cursor1 += count1; 710 len1 -= count1; 711 if (len1 <= 1) // len1 == 1 || len1 == 0 712 break outer; 713 } 714 a[dest++] = a[cursor2++]; 715 if (--len2 == 0) 716 break outer; 717 718 count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c); 719 if (count2 != 0) { 720 System.arraycopy(a, cursor2, a, dest, count2); 721 dest += count2; 722 cursor2 += count2; 723 len2 -= count2; 724 if (len2 == 0) 725 break outer; 726 } 727 a[dest++] = tmp[cursor1++]; 728 if (--len1 == 1) 729 break outer; 730 minGallop--; 731 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 732 if (minGallop < 0) 733 minGallop = 0; 734 minGallop += 2; // Penalize for leaving gallop mode 735 } // End of "outer" loop 736 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 737 738 if (len1 == 1) { 739 if (DEBUG) assert len2 > 0; 740 System.arraycopy(a, cursor2, a, dest, len2); 741 a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge 742 } else if (len1 == 0) { 743 throw new IllegalArgumentException( 744 "Comparison method violates its general contract!"); 745 } else { 746 if (DEBUG) assert len2 == 0; 747 if (DEBUG) assert len1 > 1; 748 System.arraycopy(tmp, cursor1, a, dest, len1); 749 } 750 } 751 752 /** 753 * Like mergeLo, except that this method should be called only if 754 * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method 755 * may be called if len1 == len2.) 756 * 757 * @param base1 index of first element in first run to be merged 758 * @param len1 length of first run to be merged (must be > 0) 759 * @param base2 index of first element in second run to be merged 760 * (must be aBase + aLen) 761 * @param len2 length of second run to be merged (must be > 0) 762 */ 763 private void mergeHi(int base1, int len1, int base2, int len2) { 764 if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 765 766 // Copy second run into temp array 767 T[] a = this.a; // For performance 768 T[] tmp = ensureCapacity(len2); 769 System.arraycopy(a, base2, tmp, 0, len2); 770 771 int cursor1 = base1 + len1 - 1; // Indexes into a 772 int cursor2 = len2 - 1; // Indexes into tmp array 773 int dest = base2 + len2 - 1; // Indexes into a 774 775 // Move last element of first run and deal with degenerate cases 776 a[dest--] = a[cursor1--]; 777 if (--len1 == 0) { 778 System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); 779 return; 780 } 781 if (len2 == 1) { 782 dest -= len1; 783 cursor1 -= len1; 784 System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); 785 a[dest] = tmp[cursor2]; 786 return; 787 } 788 789 Comparator<? super T> c = this.c; // Use local variable for performance 790 int minGallop = this.minGallop; // " " " " " 791 outer: 792 while (true) { 793 int count1 = 0; // Number of times in a row that first run won 794 int count2 = 0; // Number of times in a row that second run won 795 796 /* 797 * Do the straightforward thing until (if ever) one run 798 * appears to win consistently. 799 */ 800 do { 801 if (DEBUG) assert len1 > 0 && len2 > 1; 802 if (c.compare(tmp[cursor2], a[cursor1]) < 0) { 803 a[dest--] = a[cursor1--]; 804 count1++; 805 count2 = 0; 806 if (--len1 == 0) 807 break outer; 808 } else { 809 a[dest--] = tmp[cursor2--]; 810 count2++; 811 count1 = 0; 812 if (--len2 == 1) 813 break outer; 814 } 815 } while ((count1 | count2) < minGallop); 816 817 /* 818 * One run is winning so consistently that galloping may be a 819 * huge win. So try that, and continue galloping until (if ever) 820 * neither run appears to be winning consistently anymore. 821 */ 822 do { 823 if (DEBUG) assert len1 > 0 && len2 > 1; 824 count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c); 825 if (count1 != 0) { 826 dest -= count1; 827 cursor1 -= count1; 828 len1 -= count1; 829 System.arraycopy(a, cursor1 + 1, a, dest + 1, count1); 830 if (len1 == 0) 831 break outer; 832 } 833 a[dest--] = tmp[cursor2--]; 834 if (--len2 == 1) 835 break outer; 836 837 count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c); 838 if (count2 != 0) { 839 dest -= count2; 840 cursor2 -= count2; 841 len2 -= count2; 842 System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2); 843 if (len2 <= 1) // len2 == 1 || len2 == 0 844 break outer; 845 } 846 a[dest--] = a[cursor1--]; 847 if (--len1 == 0) 848 break outer; 849 minGallop--; 850 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 851 if (minGallop < 0) 852 minGallop = 0; 853 minGallop += 2; // Penalize for leaving gallop mode 854 } // End of "outer" loop 855 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 856 857 if (len2 == 1) { 858 if (DEBUG) assert len1 > 0; 859 dest -= len1; 860 cursor1 -= len1; 861 System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); 862 a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge 863 } else if (len2 == 0) { 864 throw new IllegalArgumentException( 865 "Comparison method violates its general contract!"); 866 } else { 867 if (DEBUG) assert len1 == 0; 868 if (DEBUG) assert len2 > 0; 869 System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); 870 } 871 } 872 873 /** 874 * Ensures that the external array tmp has at least the specified 875 * number of elements, increasing its size if necessary. The size 876 * increases exponentially to ensure amortized linear time complexity. 877 * 878 * @param minCapacity the minimum required capacity of the tmp array 879 * @return tmp, whether or not it grew 880 */ 881 private T[] ensureCapacity(int minCapacity) { 882 if (tmp.length < minCapacity) { 883 // Compute smallest power of 2 > minCapacity 884 int newSize = minCapacity; 885 newSize |= newSize >> 1; 886 newSize |= newSize >> 2; 887 newSize |= newSize >> 4; 888 newSize |= newSize >> 8; 889 newSize |= newSize >> 16; 890 newSize++; 891 892 if (newSize < 0) // Not bloody likely! 893 newSize = minCapacity; 894 else 895 newSize = Math.min(newSize, a.length >>> 1); 896 897 @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) 898 T[] newArray = (T[]) new Object[newSize]; 899 tmp = newArray; 900 } 901 return tmp; 902 } 903} 904