ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ComparableTimSort.java
Revision: 1.7
Committed: Fri Jun 1 14:57:28 2018 UTC (5 years, 9 months ago) by jsr166
Branch: MAIN
CVS Tags: HEAD
Changes since 1.6: +1 -1 lines
Log Message:
fix javadoc formatting

File Contents

# Content
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 */
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 */
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"})
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"})
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 * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer,
399 * Richard Bubel and Reiner Hahnle, this is fixed with respect to
400 * the analysis in "On the Worst-Case Complexity of TimSort" by
401 * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.
402 */
403 private void mergeCollapse() {
404 while (stackSize > 1) {
405 int n = stackSize - 2;
406 if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] ||
407 n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) {
408 if (runLen[n - 1] < runLen[n + 1])
409 n--;
410 } else if (n < 0 || runLen[n] > runLen[n + 1]) {
411 break; // Invariant is established
412 }
413 mergeAt(n);
414 }
415 }
416
417 /**
418 * Merges all runs on the stack until only one remains. This method is
419 * called once, to complete the sort.
420 */
421 private void mergeForceCollapse() {
422 while (stackSize > 1) {
423 int n = stackSize - 2;
424 if (n > 0 && runLen[n - 1] < runLen[n + 1])
425 n--;
426 mergeAt(n);
427 }
428 }
429
430 /**
431 * Merges the two runs at stack indices i and i+1. Run i must be
432 * the penultimate or antepenultimate run on the stack. In other words,
433 * i must be equal to stackSize-2 or stackSize-3.
434 *
435 * @param i stack index of the first of the two runs to merge
436 */
437 @SuppressWarnings("unchecked")
438 private void mergeAt(int i) {
439 assert stackSize >= 2;
440 assert i >= 0;
441 assert i == stackSize - 2 || i == stackSize - 3;
442
443 int base1 = runBase[i];
444 int len1 = runLen[i];
445 int base2 = runBase[i + 1];
446 int len2 = runLen[i + 1];
447 assert len1 > 0 && len2 > 0;
448 assert base1 + len1 == base2;
449
450 /*
451 * Record the length of the combined runs; if i is the 3rd-last
452 * run now, also slide over the last run (which isn't involved
453 * in this merge). The current run (i+1) goes away in any case.
454 */
455 runLen[i] = len1 + len2;
456 if (i == stackSize - 3) {
457 runBase[i + 1] = runBase[i + 2];
458 runLen[i + 1] = runLen[i + 2];
459 }
460 stackSize--;
461
462 /*
463 * Find where the first element of run2 goes in run1. Prior elements
464 * in run1 can be ignored (because they're already in place).
465 */
466 int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0);
467 assert k >= 0;
468 base1 += k;
469 len1 -= k;
470 if (len1 == 0)
471 return;
472
473 /*
474 * Find where the last element of run1 goes in run2. Subsequent elements
475 * in run2 can be ignored (because they're already in place).
476 */
477 len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a,
478 base2, len2, len2 - 1);
479 assert len2 >= 0;
480 if (len2 == 0)
481 return;
482
483 // Merge remaining runs, using tmp array with min(len1, len2) elements
484 if (len1 <= len2)
485 mergeLo(base1, len1, base2, len2);
486 else
487 mergeHi(base1, len1, base2, len2);
488 }
489
490 /**
491 * Locates the position at which to insert the specified key into the
492 * specified sorted range; if the range contains an element equal to key,
493 * returns the index of the leftmost equal element.
494 *
495 * @param key the key whose insertion point to search for
496 * @param a the array in which to search
497 * @param base the index of the first element in the range
498 * @param len the length of the range; must be > 0
499 * @param hint the index at which to begin the search, 0 <= hint < n.
500 * The closer hint is to the result, the faster this method will run.
501 * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
502 * pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
503 * In other words, key belongs at index b + k; or in other words,
504 * the first k elements of a should precede key, and the last n - k
505 * should follow it.
506 */
507 private static int gallopLeft(Comparable<Object> key, Object[] a,
508 int base, int len, int hint) {
509 assert len > 0 && hint >= 0 && hint < len;
510
511 int lastOfs = 0;
512 int ofs = 1;
513 if (key.compareTo(a[base + hint]) > 0) {
514 // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
515 int maxOfs = len - hint;
516 while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) > 0) {
517 lastOfs = ofs;
518 ofs = (ofs << 1) + 1;
519 if (ofs <= 0) // int overflow
520 ofs = maxOfs;
521 }
522 if (ofs > maxOfs)
523 ofs = maxOfs;
524
525 // Make offsets relative to base
526 lastOfs += hint;
527 ofs += hint;
528 } else { // key <= a[base + hint]
529 // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
530 final int maxOfs = hint + 1;
531 while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) <= 0) {
532 lastOfs = ofs;
533 ofs = (ofs << 1) + 1;
534 if (ofs <= 0) // int overflow
535 ofs = maxOfs;
536 }
537 if (ofs > maxOfs)
538 ofs = maxOfs;
539
540 // Make offsets relative to base
541 int tmp = lastOfs;
542 lastOfs = hint - ofs;
543 ofs = hint - tmp;
544 }
545 assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
546
547 /*
548 * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
549 * to the right of lastOfs but no farther right than ofs. Do a binary
550 * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
551 */
552 lastOfs++;
553 while (lastOfs < ofs) {
554 int m = lastOfs + ((ofs - lastOfs) >>> 1);
555
556 if (key.compareTo(a[base + m]) > 0)
557 lastOfs = m + 1; // a[base + m] < key
558 else
559 ofs = m; // key <= a[base + m]
560 }
561 assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs]
562 return ofs;
563 }
564
565 /**
566 * Like gallopLeft, except that if the range contains an element equal to
567 * key, gallopRight returns the index after the rightmost equal element.
568 *
569 * @param key the key whose insertion point to search for
570 * @param a the array in which to search
571 * @param base the index of the first element in the range
572 * @param len the length of the range; must be > 0
573 * @param hint the index at which to begin the search, 0 <= hint < n.
574 * The closer hint is to the result, the faster this method will run.
575 * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
576 */
577 private static int gallopRight(Comparable<Object> key, Object[] a,
578 int base, int len, int hint) {
579 assert len > 0 && hint >= 0 && hint < len;
580
581 int ofs = 1;
582 int lastOfs = 0;
583 if (key.compareTo(a[base + hint]) < 0) {
584 // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
585 int maxOfs = hint + 1;
586 while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) < 0) {
587 lastOfs = ofs;
588 ofs = (ofs << 1) + 1;
589 if (ofs <= 0) // int overflow
590 ofs = maxOfs;
591 }
592 if (ofs > maxOfs)
593 ofs = maxOfs;
594
595 // Make offsets relative to b
596 int tmp = lastOfs;
597 lastOfs = hint - ofs;
598 ofs = hint - tmp;
599 } else { // a[b + hint] <= key
600 // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
601 int maxOfs = len - hint;
602 while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) >= 0) {
603 lastOfs = ofs;
604 ofs = (ofs << 1) + 1;
605 if (ofs <= 0) // int overflow
606 ofs = maxOfs;
607 }
608 if (ofs > maxOfs)
609 ofs = maxOfs;
610
611 // Make offsets relative to b
612 lastOfs += hint;
613 ofs += hint;
614 }
615 assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
616
617 /*
618 * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
619 * the right of lastOfs but no farther right than ofs. Do a binary
620 * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
621 */
622 lastOfs++;
623 while (lastOfs < ofs) {
624 int m = lastOfs + ((ofs - lastOfs) >>> 1);
625
626 if (key.compareTo(a[base + m]) < 0)
627 ofs = m; // key < a[b + m]
628 else
629 lastOfs = m + 1; // a[b + m] <= key
630 }
631 assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
632 return ofs;
633 }
634
635 /**
636 * Merges two adjacent runs in place, in a stable fashion. The first
637 * element of the first run must be greater than the first element of the
638 * second run (a[base1] > a[base2]), and the last element of the first run
639 * (a[base1 + len1-1]) must be greater than all elements of the second run.
640 *
641 * For performance, this method should be called only when len1 <= len2;
642 * its twin, mergeHi should be called if len1 >= len2. (Either method
643 * may be called if len1 == len2.)
644 *
645 * @param base1 index of first element in first run to be merged
646 * @param len1 length of first run to be merged (must be > 0)
647 * @param base2 index of first element in second run to be merged
648 * (must be aBase + aLen)
649 * @param len2 length of second run to be merged (must be > 0)
650 */
651 @SuppressWarnings({"unchecked", "rawtypes"})
652 private void mergeLo(int base1, int len1, int base2, int len2) {
653 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
654
655 // Copy first run into temp array
656 Object[] a = this.a; // For performance
657 Object[] tmp = ensureCapacity(len1);
658
659 int cursor1 = tmpBase; // Indexes into tmp array
660 int cursor2 = base2; // Indexes int a
661 int dest = base1; // Indexes int a
662 System.arraycopy(a, base1, tmp, cursor1, len1);
663
664 // Move first element of second run and deal with degenerate cases
665 a[dest++] = a[cursor2++];
666 if (--len2 == 0) {
667 System.arraycopy(tmp, cursor1, a, dest, len1);
668 return;
669 }
670 if (len1 == 1) {
671 System.arraycopy(a, cursor2, a, dest, len2);
672 a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
673 return;
674 }
675
676 int minGallop = this.minGallop; // Use local variable for performance
677 outer:
678 while (true) {
679 int count1 = 0; // Number of times in a row that first run won
680 int count2 = 0; // Number of times in a row that second run won
681
682 /*
683 * Do the straightforward thing until (if ever) one run starts
684 * winning consistently.
685 */
686 do {
687 assert len1 > 1 && len2 > 0;
688 if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) {
689 a[dest++] = a[cursor2++];
690 count2++;
691 count1 = 0;
692 if (--len2 == 0)
693 break outer;
694 } else {
695 a[dest++] = tmp[cursor1++];
696 count1++;
697 count2 = 0;
698 if (--len1 == 1)
699 break outer;
700 }
701 } while ((count1 | count2) < minGallop);
702
703 /*
704 * One run is winning so consistently that galloping may be a
705 * huge win. So try that, and continue galloping until (if ever)
706 * neither run appears to be winning consistently anymore.
707 */
708 do {
709 assert len1 > 1 && len2 > 0;
710 count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0);
711 if (count1 != 0) {
712 System.arraycopy(tmp, cursor1, a, dest, count1);
713 dest += count1;
714 cursor1 += count1;
715 len1 -= count1;
716 if (len1 <= 1) // len1 == 1 || len1 == 0
717 break outer;
718 }
719 a[dest++] = a[cursor2++];
720 if (--len2 == 0)
721 break outer;
722
723 count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0);
724 if (count2 != 0) {
725 System.arraycopy(a, cursor2, a, dest, count2);
726 dest += count2;
727 cursor2 += count2;
728 len2 -= count2;
729 if (len2 == 0)
730 break outer;
731 }
732 a[dest++] = tmp[cursor1++];
733 if (--len1 == 1)
734 break outer;
735 minGallop--;
736 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
737 if (minGallop < 0)
738 minGallop = 0;
739 minGallop += 2; // Penalize for leaving gallop mode
740 } // End of "outer" loop
741 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
742
743 if (len1 == 1) {
744 assert len2 > 0;
745 System.arraycopy(a, cursor2, a, dest, len2);
746 a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
747 } else if (len1 == 0) {
748 throw new IllegalArgumentException(
749 "Comparison method violates its general contract!");
750 } else {
751 assert len2 == 0;
752 assert len1 > 1;
753 System.arraycopy(tmp, cursor1, a, dest, len1);
754 }
755 }
756
757 /**
758 * Like mergeLo, except that this method should be called only if
759 * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
760 * may be called if len1 == len2.)
761 *
762 * @param base1 index of first element in first run to be merged
763 * @param len1 length of first run to be merged (must be > 0)
764 * @param base2 index of first element in second run to be merged
765 * (must be aBase + aLen)
766 * @param len2 length of second run to be merged (must be > 0)
767 */
768 @SuppressWarnings({"unchecked", "rawtypes"})
769 private void mergeHi(int base1, int len1, int base2, int len2) {
770 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
771
772 // Copy second run into temp array
773 Object[] a = this.a; // For performance
774 Object[] tmp = ensureCapacity(len2);
775 int tmpBase = this.tmpBase;
776 System.arraycopy(a, base2, tmp, tmpBase, len2);
777
778 int cursor1 = base1 + len1 - 1; // Indexes into a
779 int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array
780 int dest = base2 + len2 - 1; // Indexes into a
781
782 // Move last element of first run and deal with degenerate cases
783 a[dest--] = a[cursor1--];
784 if (--len1 == 0) {
785 System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
786 return;
787 }
788 if (len2 == 1) {
789 dest -= len1;
790 cursor1 -= len1;
791 System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
792 a[dest] = tmp[cursor2];
793 return;
794 }
795
796 int minGallop = this.minGallop; // Use local variable for performance
797 outer:
798 while (true) {
799 int count1 = 0; // Number of times in a row that first run won
800 int count2 = 0; // Number of times in a row that second run won
801
802 /*
803 * Do the straightforward thing until (if ever) one run
804 * appears to win consistently.
805 */
806 do {
807 assert len1 > 0 && len2 > 1;
808 if (((Comparable) tmp[cursor2]).compareTo(a[cursor1]) < 0) {
809 a[dest--] = a[cursor1--];
810 count1++;
811 count2 = 0;
812 if (--len1 == 0)
813 break outer;
814 } else {
815 a[dest--] = tmp[cursor2--];
816 count2++;
817 count1 = 0;
818 if (--len2 == 1)
819 break outer;
820 }
821 } while ((count1 | count2) < minGallop);
822
823 /*
824 * One run is winning so consistently that galloping may be a
825 * huge win. So try that, and continue galloping until (if ever)
826 * neither run appears to be winning consistently anymore.
827 */
828 do {
829 assert len1 > 0 && len2 > 1;
830 count1 = len1 - gallopRight((Comparable) tmp[cursor2], a, base1, len1, len1 - 1);
831 if (count1 != 0) {
832 dest -= count1;
833 cursor1 -= count1;
834 len1 -= count1;
835 System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
836 if (len1 == 0)
837 break outer;
838 }
839 a[dest--] = tmp[cursor2--];
840 if (--len2 == 1)
841 break outer;
842
843 count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, tmpBase, len2, len2 - 1);
844 if (count2 != 0) {
845 dest -= count2;
846 cursor2 -= count2;
847 len2 -= count2;
848 System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
849 if (len2 <= 1)
850 break outer; // len2 == 1 || len2 == 0
851 }
852 a[dest--] = a[cursor1--];
853 if (--len1 == 0)
854 break outer;
855 minGallop--;
856 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
857 if (minGallop < 0)
858 minGallop = 0;
859 minGallop += 2; // Penalize for leaving gallop mode
860 } // End of "outer" loop
861 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
862
863 if (len2 == 1) {
864 assert len1 > 0;
865 dest -= len1;
866 cursor1 -= len1;
867 System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
868 a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
869 } else if (len2 == 0) {
870 throw new IllegalArgumentException(
871 "Comparison method violates its general contract!");
872 } else {
873 assert len1 == 0;
874 assert len2 > 0;
875 System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
876 }
877 }
878
879 /**
880 * Ensures that the external array tmp has at least the specified
881 * number of elements, increasing its size if necessary. The size
882 * increases exponentially to ensure amortized linear time complexity.
883 *
884 * @param minCapacity the minimum required capacity of the tmp array
885 * @return tmp, whether or not it grew
886 */
887 private Object[] ensureCapacity(int minCapacity) {
888 if (tmpLen < minCapacity) {
889 // Compute smallest power of 2 > minCapacity
890 int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity);
891 newSize++;
892
893 if (newSize < 0) // Not bloody likely!
894 newSize = minCapacity;
895 else
896 newSize = Math.min(newSize, a.length >>> 1);
897
898 @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
899 Object[] newArray = new Object[newSize];
900 tmp = newArray;
901 tmpLen = newSize;
902 tmpBase = 0;
903 }
904 return tmp;
905 }
906
907 }