14 |
|
* limitations under the License. |
15 |
|
*/ |
16 |
|
|
17 |
< |
import java.util.*; |
17 |
> |
package java.util; |
18 |
|
|
19 |
|
/** |
20 |
|
* A stable, adaptive, iterative mergesort that requires far fewer than |
46 |
|
* (privately) instantiable; a TimSort instance holds the state of an ongoing |
47 |
|
* sort, assuming the input array is large enough to warrant the full-blown |
48 |
|
* TimSort. Small arrays are sorted in place, using a binary insertion sort. |
49 |
+ |
* |
50 |
+ |
* @author Josh Bloch |
51 |
|
*/ |
52 |
|
class TimSort<T> { |
53 |
|
/** |
177 |
|
|
178 |
|
// If array is small, do a "mini-TimSort" with no merges |
179 |
|
if (nRemaining < MIN_MERGE) { |
180 |
< |
int initRunLen = countRunAndMakeAscending(a, lo, nRemaining, c); |
180 |
> |
int initRunLen = countRunAndMakeAscending(a, lo, hi, c); |
181 |
|
binarySort(a, lo, hi, lo + initRunLen, c); |
182 |
|
return; |
183 |
|
} |
230 |
|
* @param lo the index of the first element in the range to be sorted |
231 |
|
* @param hi the index after the last element in the range to be sorted |
232 |
|
* @param start the index of the first element in the range that is |
233 |
< |
* not already known to be sorted (@code lo <= start <= hi} |
233 |
> |
* not already known to be sorted ({@code lo <= start <= hi}) |
234 |
|
* @param c comparator to used for the sort |
235 |
|
*/ |
236 |
|
@SuppressWarnings("fallthrough") |
269 |
|
*/ |
270 |
|
int n = start - left; // The number of elements to move |
271 |
|
// Switch is just an optimization for arraycopy in default case |
272 |
< |
switch(n) { |
272 |
> |
switch (n) { |
273 |
|
case 2: a[left + 2] = a[left + 1]; |
274 |
|
case 1: a[left + 1] = a[left]; |
275 |
|
break; |
299 |
|
* @param a the array in which a run is to be counted and possibly reversed |
300 |
|
* @param lo index of the first element in the run |
301 |
|
* @param hi index after the last element that may be contained in the run. |
302 |
< |
It is required that @code{lo < hi}. |
302 |
> |
It is required that {@code lo < hi}. |
303 |
|
* @param c the comparator to used for the sort |
304 |
|
* @return the length of the run beginning at the specified position in |
305 |
|
* the specified array |
313 |
|
|
314 |
|
// Find end of run, and reverse range if descending |
315 |
|
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending |
316 |
< |
while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) |
316 |
> |
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) |
317 |
|
runHi++; |
318 |
|
reverseRange(a, lo, runHi); |
319 |
|
} else { // Ascending |
336 |
|
while (lo < hi) { |
337 |
|
Object t = a[lo]; |
338 |
|
a[lo++] = a[hi]; |
339 |
< |
a[hi--] = t; |
339 |
> |
a[hi--] = t; |
340 |
|
} |
341 |
|
} |
342 |
|
|