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