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.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * 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. A workspace array may optionally be
 115      * provided in constructor, and if so will be used as long as it
 116      * is big enough.
 117      */
 118     private T[] tmp;
 119     private int tmpBase; // base of tmp array slice
 120     private int tmpLen;  // length of tmp array slice
 121 
 122     /**
 123      * A stack of pending runs yet to be merged.  Run i starts at
 124      * address base[i] and extends for len[i] elements.  It's always
 125      * true (so long as the indices are in bounds) that:
 126      *
 127      *     runBase[i] + runLen[i] == runBase[i + 1]
 128      *
 129      * so we could cut the storage for this, but it's a minor amount,
 130      * and keeping all the info explicit simplifies the code.
 131      */
 132     private int stackSize = 0;  // Number of pending runs on stack
 133     private final int[] runBase;
 134     private final int[] runLen;
 135 
 136     /**
 137      * Creates a TimSort instance to maintain the state of an ongoing sort.
 138      *
 139      * @param a the array to be sorted
 140      * @param c the comparator to determine the order of the sort
 141      * @param work a workspace array (slice)
 142      * @param workBase origin of usable space in work array
 143      * @param workLen usable size of work array
 144      */
 145     private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) {
 146         this.a = a;
 147         this.c = c;
 148 
 149         // Allocate temp storage (which may be increased later if necessary)
 150         int len = a.length;
 151         int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
 152             len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
 153         if (work == null || workLen < tlen || workBase + tlen > work.length) {
 154             @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
 155             T[] newArray = (T[])java.lang.reflect.Array.newInstance
 156                 (a.getClass().getComponentType(), tlen);
 157             tmp = newArray;
 158             tmpBase = 0;
 159             tmpLen = tlen;
 160         }
 161         else {
 162             tmp = work;
 163             tmpBase = workBase;
 164             tmpLen = workLen;
 165         }
 166 
 167         /*
 168          * Allocate runs-to-be-merged stack (which cannot be expanded).  The
 169          * stack length requirements are described in listsort.txt.  The C
 170          * version always uses the same stack length (85), but this was
 171          * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
 172          * 100 elements) in Java.  Therefore, we use smaller (but sufficiently
 173          * large) stack lengths for smaller arrays.  The "magic numbers" in the
 174          * computation below must be changed if MIN_MERGE is decreased.  See
 175          * the MIN_MERGE declaration above for more information.
 176          */
 177         int stackLen = (len <    120  ?  5 :
 178                         len <   1542  ? 10 :
 179                         len < 119151  ? 19 : 40);
 180         runBase = new int[stackLen];
 181         runLen = new int[stackLen];
 182     }
 183 
 184     /*
 185      * The next method (package private and static) constitutes the
 186      * entire API of this class. 
 187      */
 188 
 189     /**
 190      * Sorts the given range, using the given workspace array slice
 191      * for temp storage when possible. This method is designed to be
 192      * invoked from public methods (in class Arrays) after performing
 193      * any necessary array bounds checks and expanding parameters into
 194      * the required forms.
 195      *
 196      * @param a the array to be sorted
 197      * @param lo the index of the first element, inclusive, to be sorted
 198      * @param hi the index of the last element, exclusive, to be sorted
 199      * @param c the comparator to use
 200      * @param work a workspace array (slice)
 201      * @param workBase origin of usable space in work array
 202      * @param workLen usable size of work array
 203      * @since 1.8
 204      */
 205     static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
 206                          T[] work, int workBase, int workLen) {
 207         assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
 208 
 209         int nRemaining  = hi - lo;
 210         if (nRemaining < 2)
 211             return;  // Arrays of size 0 and 1 are always sorted
 212 
 213         // If array is small, do a "mini-TimSort" with no merges
 214         if (nRemaining < MIN_MERGE) {
 215             int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
 216             binarySort(a, lo, hi, lo + initRunLen, c);
 217             return;
 218         }
 219 
 220         /**
 221          * March over the array once, left to right, finding natural runs,
 222          * extending short natural runs to minRun elements, and merging runs
 223          * to maintain stack invariant.
 224          */
 225         TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
 226         int minRun = minRunLength(nRemaining);
 227         do {
 228             // Identify next run
 229             int runLen = countRunAndMakeAscending(a, lo, hi, c);
 230 
 231             // If run is short, extend to min(minRun, nRemaining)
 232             if (runLen < minRun) {
 233                 int force = nRemaining <= minRun ? nRemaining : minRun;
 234                 binarySort(a, lo, lo + force, lo + runLen, c);
 235                 runLen = force;
 236             }
 237 
 238             // Push run onto pending-run stack, and maybe merge
 239             ts.pushRun(lo, runLen);
 240             ts.mergeCollapse();
 241 
 242             // Advance to find next run
 243             lo += runLen;
 244             nRemaining -= runLen;
 245         } while (nRemaining != 0);
 246 
 247         // Merge all remaining runs to complete sort
 248         assert lo == hi;
 249         ts.mergeForceCollapse();
 250         assert ts.stackSize == 1;
 251     }
 252 
 253     /**
 254      * Sorts the specified portion of the specified array using a binary
 255      * insertion sort.  This is the best method for sorting small numbers
 256      * of elements.  It requires O(n log n) compares, but O(n^2) data
 257      * movement (worst case).
 258      *
 259      * If the initial part of the specified range is already sorted,
 260      * this method can take advantage of it: the method assumes that the
 261      * elements from index {@code lo}, inclusive, to {@code start},
 262      * exclusive are already sorted.
 263      *
 264      * @param a the array in which a range is to be sorted
 265      * @param lo the index of the first element in the range to be sorted
 266      * @param hi the index after the last element in the range to be sorted
 267      * @param start the index of the first element in the range that is
 268      *        not already known to be sorted ({@code lo <= start <= hi})
 269      * @param c comparator to used for the sort
 270      */
 271     @SuppressWarnings("fallthrough")
 272     private static <T> void binarySort(T[] a, int lo, int hi, int start,
 273                                        Comparator<? super T> c) {
 274         assert lo <= start && start <= hi;
 275         if (start == lo)
 276             start++;
 277         for ( ; start < hi; start++) {
 278             T pivot = a[start];
 279 
 280             // Set left (and right) to the index where a[start] (pivot) belongs
 281             int left = lo;
 282             int right = start;
 283             assert left <= right;
 284             /*
 285              * Invariants:
 286              *   pivot >= all in [lo, left).
 287              *   pivot <  all in [right, start).
 288              */
 289             while (left < right) {
 290                 int mid = (left + right) >>> 1;
 291                 if (c.compare(pivot, a[mid]) < 0)
 292                     right = mid;
 293                 else
 294                     left = mid + 1;
 295             }
 296             assert left == right;
 297 
 298             /*
 299              * The invariants still hold: pivot >= all in [lo, left) and
 300              * pivot < all in [left, start), so pivot belongs at left.  Note
 301              * that if there are elements equal to pivot, left points to the
 302              * first slot after them -- that's why this sort is stable.
 303              * Slide elements over to make room for pivot.
 304              */
 305             int n = start - left;  // The number of elements to move
 306             // Switch is just an optimization for arraycopy in default case
 307             switch (n) {
 308                 case 2:  a[left + 2] = a[left + 1];
 309                 case 1:  a[left + 1] = a[left];
 310                          break;
 311                 default: System.arraycopy(a, left, a, left + 1, n);
 312             }
 313             a[left] = pivot;
 314         }
 315     }
 316 
 317     /**
 318      * Returns the length of the run beginning at the specified position in
 319      * the specified array and reverses the run if it is descending (ensuring
 320      * that the run will always be ascending when the method returns).
 321      *
 322      * A run is the longest ascending sequence with:
 323      *
 324      *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
 325      *
 326      * or the longest descending sequence with:
 327      *
 328      *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 329      *
 330      * For its intended use in a stable mergesort, the strictness of the
 331      * definition of "descending" is needed so that the call can safely
 332      * reverse a descending sequence without violating stability.
 333      *
 334      * @param a the array in which a run is to be counted and possibly reversed
 335      * @param lo index of the first element in the run
 336      * @param hi index after the last element that may be contained in the run.
 337               It is required that {@code lo < hi}.
 338      * @param c the comparator to used for the sort
 339      * @return  the length of the run beginning at the specified position in
 340      *          the specified array
 341      */
 342     private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
 343                                                     Comparator<? super T> c) {
 344         assert lo < hi;
 345         int runHi = lo + 1;
 346         if (runHi == hi)
 347             return 1;
 348 
 349         // Find end of run, and reverse range if descending
 350         if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
 351             while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
 352                 runHi++;
 353             reverseRange(a, lo, runHi);
 354         } else {                              // Ascending
 355             while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
 356                 runHi++;
 357         }
 358 
 359         return runHi - lo;
 360     }
 361 
 362     /**
 363      * Reverse the specified range of the specified array.
 364      *
 365      * @param a the array in which a range is to be reversed
 366      * @param lo the index of the first element in the range to be reversed
 367      * @param hi the index after the last element in the range to be reversed
 368      */
 369     private static void reverseRange(Object[] a, int lo, int hi) {
 370         hi--;
 371         while (lo < hi) {
 372             Object t = a[lo];
 373             a[lo++] = a[hi];
 374             a[hi--] = t;
 375         }
 376     }
 377 
 378     /**
 379      * Returns the minimum acceptable run length for an array of the specified
 380      * length. Natural runs shorter than this will be extended with
 381      * {@link #binarySort}.
 382      *
 383      * Roughly speaking, the computation is:
 384      *
 385      *  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
 386      *  Else if n is an exact power of 2, return MIN_MERGE/2.
 387      *  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
 388      *   is close to, but strictly less than, an exact power of 2.
 389      *
 390      * For the rationale, see listsort.txt.
 391      *
 392      * @param n the length of the array to be sorted
 393      * @return the length of the minimum run to be merged
 394      */
 395     private static int minRunLength(int n) {
 396         assert n >= 0;
 397         int r = 0;      // Becomes 1 if any 1 bits are shifted off
 398         while (n >= MIN_MERGE) {
 399             r |= (n & 1);
 400             n >>= 1;
 401         }
 402         return n + r;
 403     }
 404 
 405     /**
 406      * Pushes the specified run onto the pending-run stack.
 407      *
 408      * @param runBase index of the first element in the run
 409      * @param runLen  the number of elements in the run
 410      */
 411     private void pushRun(int runBase, int runLen) {
 412         this.runBase[stackSize] = runBase;
 413         this.runLen[stackSize] = runLen;
 414         stackSize++;
 415     }
 416 
 417     /**
 418      * Examines the stack of runs waiting to be merged and merges adjacent runs
 419      * until the stack invariants are reestablished:
 420      *
 421      *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
 422      *     2. runLen[i - 2] > runLen[i - 1]
 423      *
 424      * This method is called each time a new run is pushed onto the stack,
 425      * so the invariants are guaranteed to hold for i < stackSize upon
 426      * entry to the method.
 427      */
 428     private void mergeCollapse() {
 429         while (stackSize > 1) {
 430             int n = stackSize - 2;
 431             if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
 432                 if (runLen[n - 1] < runLen[n + 1])
 433                     n--;
 434                 mergeAt(n);
 435             } else if (runLen[n] <= runLen[n + 1]) {
 436                 mergeAt(n);
 437             } else {
 438                 break; // Invariant is established
 439             }
 440         }
 441     }
 442 
 443     /**
 444      * Merges all runs on the stack until only one remains.  This method is
 445      * called once, to complete the sort.
 446      */
 447     private void mergeForceCollapse() {
 448         while (stackSize > 1) {
 449             int n = stackSize - 2;
 450             if (n > 0 && runLen[n - 1] < runLen[n + 1])
 451                 n--;
 452             mergeAt(n);
 453         }
 454     }
 455 
 456     /**
 457      * Merges the two runs at stack indices i and i+1.  Run i must be
 458      * the penultimate or antepenultimate run on the stack.  In other words,
 459      * i must be equal to stackSize-2 or stackSize-3.
 460      *
 461      * @param i stack index of the first of the two runs to merge
 462      */
 463     private void mergeAt(int i) {
 464         assert stackSize >= 2;
 465         assert i >= 0;
 466         assert i == stackSize - 2 || i == stackSize - 3;
 467 
 468         int base1 = runBase[i];
 469         int len1 = runLen[i];
 470         int base2 = runBase[i + 1];
 471         int len2 = runLen[i + 1];
 472         assert len1 > 0 && len2 > 0;
 473         assert base1 + len1 == base2;
 474 
 475         /*
 476          * Record the length of the combined runs; if i is the 3rd-last
 477          * run now, also slide over the last run (which isn't involved
 478          * in this merge).  The current run (i+1) goes away in any case.
 479          */
 480         runLen[i] = len1 + len2;
 481         if (i == stackSize - 3) {
 482             runBase[i + 1] = runBase[i + 2];
 483             runLen[i + 1] = runLen[i + 2];
 484         }
 485         stackSize--;
 486 
 487         /*
 488          * Find where the first element of run2 goes in run1. Prior elements
 489          * in run1 can be ignored (because they're already in place).
 490          */
 491         int k = gallopRight(a[base2], a, base1, len1, 0, c);
 492         assert k >= 0;
 493         base1 += k;
 494         len1 -= k;
 495         if (len1 == 0)
 496             return;
 497 
 498         /*
 499          * Find where the last element of run1 goes in run2. Subsequent elements
 500          * in run2 can be ignored (because they're already in place).
 501          */
 502         len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
 503         assert len2 >= 0;
 504         if (len2 == 0)
 505             return;
 506 
 507         // Merge remaining runs, using tmp array with min(len1, len2) elements
 508         if (len1 <= len2)
 509             mergeLo(base1, len1, base2, len2);
 510         else
 511             mergeHi(base1, len1, base2, len2);
 512     }
 513 
 514     /**
 515      * Locates the position at which to insert the specified key into the
 516      * specified sorted range; if the range contains an element equal to key,
 517      * returns the index of the leftmost equal element.
 518      *
 519      * @param key the key whose insertion point to search for
 520      * @param a the array in which to search
 521      * @param base the index of the first element in the range
 522      * @param len the length of the range; must be > 0
 523      * @param hint the index at which to begin the search, 0 <= hint < n.
 524      *     The closer hint is to the result, the faster this method will run.
 525      * @param c the comparator used to order the range, and to search
 526      * @return the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
 527      *    pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
 528      *    In other words, key belongs at index b + k; or in other words,
 529      *    the first k elements of a should precede key, and the last n - k
 530      *    should follow it.
 531      */
 532     private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
 533                                       Comparator<? super T> c) {
 534         assert len > 0 && hint >= 0 && hint < len;
 535         int lastOfs = 0;
 536         int ofs = 1;
 537         if (c.compare(key, a[base + hint]) > 0) {
 538             // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
 539             int maxOfs = len - hint;
 540             while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) {
 541                 lastOfs = ofs;
 542                 ofs = (ofs << 1) + 1;
 543                 if (ofs <= 0)   // int overflow
 544                     ofs = maxOfs;
 545             }
 546             if (ofs > maxOfs)
 547                 ofs = maxOfs;
 548 
 549             // Make offsets relative to base
 550             lastOfs += hint;
 551             ofs += hint;
 552         } else { // key <= a[base + hint]
 553             // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
 554             final int maxOfs = hint + 1;
 555             while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) {
 556                 lastOfs = ofs;
 557                 ofs = (ofs << 1) + 1;
 558                 if (ofs <= 0)   // int overflow
 559                     ofs = maxOfs;
 560             }
 561             if (ofs > maxOfs)
 562                 ofs = maxOfs;
 563 
 564             // Make offsets relative to base
 565             int tmp = lastOfs;
 566             lastOfs = hint - ofs;
 567             ofs = hint - tmp;
 568         }
 569         assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
 570 
 571         /*
 572          * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
 573          * to the right of lastOfs but no farther right than ofs.  Do a binary
 574          * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
 575          */
 576         lastOfs++;
 577         while (lastOfs < ofs) {
 578             int m = lastOfs + ((ofs - lastOfs) >>> 1);
 579 
 580             if (c.compare(key, a[base + m]) > 0)
 581                 lastOfs = m + 1;  // a[base + m] < key
 582             else
 583                 ofs = m;          // key <= a[base + m]
 584         }
 585         assert lastOfs == ofs;    // so a[base + ofs - 1] < key <= a[base + ofs]
 586         return ofs;
 587     }
 588 
 589     /**
 590      * Like gallopLeft, except that if the range contains an element equal to
 591      * key, gallopRight returns the index after the rightmost equal element.
 592      *
 593      * @param key the key whose insertion point to search for
 594      * @param a the array in which to search
 595      * @param base the index of the first element in the range
 596      * @param len the length of the range; must be > 0
 597      * @param hint the index at which to begin the search, 0 <= hint < n.
 598      *     The closer hint is to the result, the faster this method will run.
 599      * @param c the comparator used to order the range, and to search
 600      * @return the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
 601      */
 602     private static <T> int gallopRight(T key, T[] a, int base, int len,
 603                                        int hint, Comparator<? super T> c) {
 604         assert len > 0 && hint >= 0 && hint < len;
 605 
 606         int ofs = 1;
 607         int lastOfs = 0;
 608         if (c.compare(key, a[base + hint]) < 0) {
 609             // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
 610             int maxOfs = hint + 1;
 611             while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) {
 612                 lastOfs = ofs;
 613                 ofs = (ofs << 1) + 1;
 614                 if (ofs <= 0)   // int overflow
 615                     ofs = maxOfs;
 616             }
 617             if (ofs > maxOfs)
 618                 ofs = maxOfs;
 619 
 620             // Make offsets relative to b
 621             int tmp = lastOfs;
 622             lastOfs = hint - ofs;
 623             ofs = hint - tmp;
 624         } else { // a[b + hint] <= key
 625             // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
 626             int maxOfs = len - hint;
 627             while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) {
 628                 lastOfs = ofs;
 629                 ofs = (ofs << 1) + 1;
 630                 if (ofs <= 0)   // int overflow
 631                     ofs = maxOfs;
 632             }
 633             if (ofs > maxOfs)
 634                 ofs = maxOfs;
 635 
 636             // Make offsets relative to b
 637             lastOfs += hint;
 638             ofs += hint;
 639         }
 640         assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
 641 
 642         /*
 643          * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
 644          * the right of lastOfs but no farther right than ofs.  Do a binary
 645          * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
 646          */
 647         lastOfs++;
 648         while (lastOfs < ofs) {
 649             int m = lastOfs + ((ofs - lastOfs) >>> 1);
 650 
 651             if (c.compare(key, a[base + m]) < 0)
 652                 ofs = m;          // key < a[b + m]
 653             else
 654                 lastOfs = m + 1;  // a[b + m] <= key
 655         }
 656         assert lastOfs == ofs;    // so a[b + ofs - 1] <= key < a[b + ofs]
 657         return ofs;
 658     }
 659 
 660     /**
 661      * Merges two adjacent runs in place, in a stable fashion.  The first
 662      * element of the first run must be greater than the first element of the
 663      * second run (a[base1] > a[base2]), and the last element of the first run
 664      * (a[base1 + len1-1]) must be greater than all elements of the second run.
 665      *
 666      * For performance, this method should be called only when len1 <= len2;
 667      * its twin, mergeHi should be called if len1 >= len2.  (Either method
 668      * may be called if len1 == len2.)
 669      *
 670      * @param base1 index of first element in first run to be merged
 671      * @param len1  length of first run to be merged (must be > 0)
 672      * @param base2 index of first element in second run to be merged
 673      *        (must be aBase + aLen)
 674      * @param len2  length of second run to be merged (must be > 0)
 675      */
 676     private void mergeLo(int base1, int len1, int base2, int len2) {
 677         assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
 678 
 679         // Copy first run into temp array
 680         T[] a = this.a; // For performance
 681         T[] tmp = ensureCapacity(len1);
 682         int cursor1 = tmpBase; // Indexes into tmp array
 683         int cursor2 = base2;   // Indexes int a
 684         int dest = base1;      // Indexes int a
 685         System.arraycopy(a, base1, tmp, cursor1, len1);
 686 
 687         // Move first element of second run and deal with degenerate cases
 688         a[dest++] = a[cursor2++];
 689         if (--len2 == 0) {
 690             System.arraycopy(tmp, cursor1, a, dest, len1);
 691             return;
 692         }
 693         if (len1 == 1) {
 694             System.arraycopy(a, cursor2, a, dest, len2);
 695             a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
 696             return;
 697         }
 698 
 699         Comparator<? super T> c = this.c;  // Use local variable for performance
 700         int minGallop = this.minGallop;    //  "    "       "     "      "
 701     outer:
 702         while (true) {
 703             int count1 = 0; // Number of times in a row that first run won
 704             int count2 = 0; // Number of times in a row that second run won
 705 
 706             /*
 707              * Do the straightforward thing until (if ever) one run starts
 708              * winning consistently.
 709              */
 710             do {
 711                 assert len1 > 1 && len2 > 0;
 712                 if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
 713                     a[dest++] = a[cursor2++];
 714                     count2++;
 715                     count1 = 0;
 716                     if (--len2 == 0)
 717                         break outer;
 718                 } else {
 719                     a[dest++] = tmp[cursor1++];
 720                     count1++;
 721                     count2 = 0;
 722                     if (--len1 == 1)
 723                         break outer;
 724                 }
 725             } while ((count1 | count2) < minGallop);
 726 
 727             /*
 728              * One run is winning so consistently that galloping may be a
 729              * huge win. So try that, and continue galloping until (if ever)
 730              * neither run appears to be winning consistently anymore.
 731              */
 732             do {
 733                 assert len1 > 1 && len2 > 0;
 734                 count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
 735                 if (count1 != 0) {
 736                     System.arraycopy(tmp, cursor1, a, dest, count1);
 737                     dest += count1;
 738                     cursor1 += count1;
 739                     len1 -= count1;
 740                     if (len1 <= 1) // len1 == 1 || len1 == 0
 741                         break outer;
 742                 }
 743                 a[dest++] = a[cursor2++];
 744                 if (--len2 == 0)
 745                     break outer;
 746 
 747                 count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
 748                 if (count2 != 0) {
 749                     System.arraycopy(a, cursor2, a, dest, count2);
 750                     dest += count2;
 751                     cursor2 += count2;
 752                     len2 -= count2;
 753                     if (len2 == 0)
 754                         break outer;
 755                 }
 756                 a[dest++] = tmp[cursor1++];
 757                 if (--len1 == 1)
 758                     break outer;
 759                 minGallop--;
 760             } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
 761             if (minGallop < 0)
 762                 minGallop = 0;
 763             minGallop += 2;  // Penalize for leaving gallop mode
 764         }  // End of "outer" loop
 765         this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
 766 
 767         if (len1 == 1) {
 768             assert len2 > 0;
 769             System.arraycopy(a, cursor2, a, dest, len2);
 770             a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
 771         } else if (len1 == 0) {
 772             throw new IllegalArgumentException(
 773                 "Comparison method violates its general contract!");
 774         } else {
 775             assert len2 == 0;
 776             assert len1 > 1;
 777             System.arraycopy(tmp, cursor1, a, dest, len1);
 778         }
 779     }
 780 
 781     /**
 782      * Like mergeLo, except that this method should be called only if
 783      * len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
 784      * may be called if len1 == len2.)
 785      *
 786      * @param base1 index of first element in first run to be merged
 787      * @param len1  length of first run to be merged (must be > 0)
 788      * @param base2 index of first element in second run to be merged
 789      *        (must be aBase + aLen)
 790      * @param len2  length of second run to be merged (must be > 0)
 791      */
 792     private void mergeHi(int base1, int len1, int base2, int len2) {
 793         assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
 794 
 795         // Copy second run into temp array
 796         T[] a = this.a; // For performance
 797         T[] tmp = ensureCapacity(len2);
 798         int tmpBase = this.tmpBase;
 799         System.arraycopy(a, base2, tmp, tmpBase, len2);
 800 
 801         int cursor1 = base1 + len1 - 1;  // Indexes into a
 802         int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array
 803         int dest = base2 + len2 - 1;     // Indexes into a
 804 
 805         // Move last element of first run and deal with degenerate cases
 806         a[dest--] = a[cursor1--];
 807         if (--len1 == 0) {
 808             System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
 809             return;
 810         }
 811         if (len2 == 1) {
 812             dest -= len1;
 813             cursor1 -= len1;
 814             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
 815             a[dest] = tmp[cursor2];
 816             return;
 817         }
 818 
 819         Comparator<? super T> c = this.c;  // Use local variable for performance
 820         int minGallop = this.minGallop;    //  "    "       "     "      "
 821     outer:
 822         while (true) {
 823             int count1 = 0; // Number of times in a row that first run won
 824             int count2 = 0; // Number of times in a row that second run won
 825 
 826             /*
 827              * Do the straightforward thing until (if ever) one run
 828              * appears to win consistently.
 829              */
 830             do {
 831                 assert len1 > 0 && len2 > 1;
 832                 if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
 833                     a[dest--] = a[cursor1--];
 834                     count1++;
 835                     count2 = 0;
 836                     if (--len1 == 0)
 837                         break outer;
 838                 } else {
 839                     a[dest--] = tmp[cursor2--];
 840                     count2++;
 841                     count1 = 0;
 842                     if (--len2 == 1)
 843                         break outer;
 844                 }
 845             } while ((count1 | count2) < minGallop);
 846 
 847             /*
 848              * One run is winning so consistently that galloping may be a
 849              * huge win. So try that, and continue galloping until (if ever)
 850              * neither run appears to be winning consistently anymore.
 851              */
 852             do {
 853                 assert len1 > 0 && len2 > 1;
 854                 count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
 855                 if (count1 != 0) {
 856                     dest -= count1;
 857                     cursor1 -= count1;
 858                     len1 -= count1;
 859                     System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
 860                     if (len1 == 0)
 861                         break outer;
 862                 }
 863                 a[dest--] = tmp[cursor2--];
 864                 if (--len2 == 1)
 865                     break outer;
 866 
 867                 count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c);
 868                 if (count2 != 0) {
 869                     dest -= count2;
 870                     cursor2 -= count2;
 871                     len2 -= count2;
 872                     System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
 873                     if (len2 <= 1)  // len2 == 1 || len2 == 0
 874                         break outer;
 875                 }
 876                 a[dest--] = a[cursor1--];
 877                 if (--len1 == 0)
 878                     break outer;
 879                 minGallop--;
 880             } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
 881             if (minGallop < 0)
 882                 minGallop = 0;
 883             minGallop += 2;  // Penalize for leaving gallop mode
 884         }  // End of "outer" loop
 885         this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
 886 
 887         if (len2 == 1) {
 888             assert len1 > 0;
 889             dest -= len1;
 890             cursor1 -= len1;
 891             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
 892             a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge
 893         } else if (len2 == 0) {
 894             throw new IllegalArgumentException(
 895                 "Comparison method violates its general contract!");
 896         } else {
 897             assert len1 == 0;
 898             assert len2 > 0;
 899             System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
 900         }
 901     }
 902 
 903     /**
 904      * Ensures that the external array tmp has at least the specified
 905      * number of elements, increasing its size if necessary.  The size
 906      * increases exponentially to ensure amortized linear time complexity.
 907      *
 908      * @param minCapacity the minimum required capacity of the tmp array
 909      * @return tmp, whether or not it grew
 910      */
 911     private T[] ensureCapacity(int minCapacity) {
 912         if (tmpLen < minCapacity) {
 913             // Compute smallest power of 2 > minCapacity
 914             int newSize = minCapacity;
 915             newSize |= newSize >> 1;
 916             newSize |= newSize >> 2;
 917             newSize |= newSize >> 4;
 918             newSize |= newSize >> 8;
 919             newSize |= newSize >> 16;
 920             newSize++;
 921 
 922             if (newSize < 0) // Not bloody likely!
 923                 newSize = minCapacity;
 924             else
 925                 newSize = Math.min(newSize, a.length >>> 1);
 926 
 927             @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
 928             T[] newArray = (T[])java.lang.reflect.Array.newInstance
 929                 (a.getClass().getComponentType(), newSize);
 930             tmp = newArray;
 931             tmpLen = newSize;
 932             tmpBase = 0;
 933         }
 934         return tmp;
 935     }
 936 }