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