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