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