< prev index next >

src/java.base/share/classes/java/util/TimSort.java

Print this page




   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     /**


 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          */


 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);


 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


 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]


 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;


 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++;


 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++;


 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 }


   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 javany.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<any 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     /**


 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 = new T[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          */


 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 <any 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);


 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 <any 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: Any.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 <any 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 <any T> void reverseRange(T[] a, int lo, int hi) {
 370         hi--;
 371         while (lo < hi) {
 372             T 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


 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 <any 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]


 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 <any 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;


 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         Any.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             Any.arraycopy(tmp, cursor1, a, dest, len1);
 691             return;
 692         }
 693         if (len1 == 1) {
 694             Any.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++;


 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                     Any.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                     Any.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             Any.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             Any.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         Any.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             Any.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
 809             return;
 810         }
 811         if (len2 == 1) {
 812             dest -= len1;
 813             cursor1 -= len1;
 814             Any.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++;


 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                     Any.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                     Any.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             Any.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             Any.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 = new T[newSize];

 929             tmp = newArray;
 930             tmpLen = newSize;
 931             tmpBase = 0;
 932         }
 933         return tmp;
 934     }
 935 }
< prev index next >