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