191 assert ts.stackSize == 1;
192 }
193
194 /**
195 * Sorts the specified portion of the specified array using a binary
196 * insertion sort. This is the best method for sorting small numbers
197 * of elements. It requires O(n log n) compares, but O(n^2) data
198 * movement (worst case).
199 *
200 * If the initial part of the specified range is already sorted,
201 * this method can take advantage of it: the method assumes that the
202 * elements from index {@code lo}, inclusive, to {@code start},
203 * exclusive are already sorted.
204 *
205 * @param a the array in which a range is to be sorted
206 * @param lo the index of the first element in the range to be sorted
207 * @param hi the index after the last element in the range to be sorted
208 * @param start the index of the first element in the range that is
209 * not already known to be sorted ({@code lo <= start <= hi})
210 */
211 @SuppressWarnings({ "fallthrough", "rawtypes", "unchecked" })
212 private static void binarySort(Object[] a, int lo, int hi, int start) {
213 assert lo <= start && start <= hi;
214 if (start == lo)
215 start++;
216 for ( ; start < hi; start++) {
217 Comparable pivot = (Comparable) a[start];
218
219 // Set left (and right) to the index where a[start] (pivot) belongs
220 int left = lo;
221 int right = start;
222 assert left <= right;
223 /*
224 * Invariants:
225 * pivot >= all in [lo, left).
226 * pivot < all in [right, start).
227 */
228 while (left < right) {
229 int mid = (left + right) >>> 1;
230 if (pivot.compareTo(a[mid]) < 0)
231 right = mid;
260 *
261 * A run is the longest ascending sequence with:
262 *
263 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
264 *
265 * or the longest descending sequence with:
266 *
267 * a[lo] > a[lo + 1] > a[lo + 2] > ...
268 *
269 * For its intended use in a stable mergesort, the strictness of the
270 * definition of "descending" is needed so that the call can safely
271 * reverse a descending sequence without violating stability.
272 *
273 * @param a the array in which a run is to be counted and possibly reversed
274 * @param lo index of the first element in the run
275 * @param hi index after the last element that may be contained in the run.
276 It is required that {@code lo < hi}.
277 * @return the length of the run beginning at the specified position in
278 * the specified array
279 */
280 @SuppressWarnings({ "unchecked", "rawtypes" })
281 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
282 assert lo < hi;
283 int runHi = lo + 1;
284 if (runHi == hi)
285 return 1;
286
287 // Find end of run, and reverse range if descending
288 if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
289 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
290 runHi++;
291 reverseRange(a, lo, runHi);
292 } else { // Ascending
293 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
294 runHi++;
295 }
296
297 return runHi - lo;
298 }
299
300 /**
595 assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
596 return ofs;
597 }
598
599 /**
600 * Merges two adjacent runs in place, in a stable fashion. The first
601 * element of the first run must be greater than the first element of the
602 * second run (a[base1] > a[base2]), and the last element of the first run
603 * (a[base1 + len1-1]) must be greater than all elements of the second run.
604 *
605 * For performance, this method should be called only when len1 <= len2;
606 * its twin, mergeHi should be called if len1 >= len2. (Either method
607 * may be called if len1 == len2.)
608 *
609 * @param base1 index of first element in first run to be merged
610 * @param len1 length of first run to be merged (must be > 0)
611 * @param base2 index of first element in second run to be merged
612 * (must be aBase + aLen)
613 * @param len2 length of second run to be merged (must be > 0)
614 */
615 @SuppressWarnings({ "unchecked", "rawtypes" })
616 private void mergeLo(int base1, int len1, int base2, int len2) {
617 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
618
619 // Copy first run into temp array
620 Object[] a = this.a; // For performance
621 Object[] tmp = ensureCapacity(len1);
622 System.arraycopy(a, base1, tmp, 0, len1);
623
624 int cursor1 = 0; // Indexes into tmp array
625 int cursor2 = base2; // Indexes int a
626 int dest = base1; // Indexes int a
627
628 // Move first element of second run and deal with degenerate cases
629 a[dest++] = a[cursor2++];
630 if (--len2 == 0) {
631 System.arraycopy(tmp, cursor1, a, dest, len1);
632 return;
633 }
634 if (len1 == 1) {
635 System.arraycopy(a, cursor2, a, dest, len2);
712 throw new IllegalArgumentException(
713 "Comparison method violates its general contract!");
714 } else {
715 assert len2 == 0;
716 assert len1 > 1;
717 System.arraycopy(tmp, cursor1, a, dest, len1);
718 }
719 }
720
721 /**
722 * Like mergeLo, except that this method should be called only if
723 * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
724 * may be called if len1 == len2.)
725 *
726 * @param base1 index of first element in first run to be merged
727 * @param len1 length of first run to be merged (must be > 0)
728 * @param base2 index of first element in second run to be merged
729 * (must be aBase + aLen)
730 * @param len2 length of second run to be merged (must be > 0)
731 */
732 @SuppressWarnings({ "unchecked", "rawtypes" })
733 private void mergeHi(int base1, int len1, int base2, int len2) {
734 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
735
736 // Copy second run into temp array
737 Object[] a = this.a; // For performance
738 Object[] tmp = ensureCapacity(len2);
739 System.arraycopy(a, base2, tmp, 0, len2);
740
741 int cursor1 = base1 + len1 - 1; // Indexes into a
742 int cursor2 = len2 - 1; // Indexes into tmp array
743 int dest = base2 + len2 - 1; // Indexes into a
744
745 // Move last element of first run and deal with degenerate cases
746 a[dest--] = a[cursor1--];
747 if (--len1 == 0) {
748 System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
749 return;
750 }
751 if (len2 == 1) {
752 dest -= len1;
|
191 assert ts.stackSize == 1;
192 }
193
194 /**
195 * Sorts the specified portion of the specified array using a binary
196 * insertion sort. This is the best method for sorting small numbers
197 * of elements. It requires O(n log n) compares, but O(n^2) data
198 * movement (worst case).
199 *
200 * If the initial part of the specified range is already sorted,
201 * this method can take advantage of it: the method assumes that the
202 * elements from index {@code lo}, inclusive, to {@code start},
203 * exclusive are already sorted.
204 *
205 * @param a the array in which a range is to be sorted
206 * @param lo the index of the first element in the range to be sorted
207 * @param hi the index after the last element in the range to be sorted
208 * @param start the index of the first element in the range that is
209 * not already known to be sorted ({@code lo <= start <= hi})
210 */
211 @SuppressWarnings({"fallthrough", "rawtypes", "unchecked"})
212 private static void binarySort(Object[] a, int lo, int hi, int start) {
213 assert lo <= start && start <= hi;
214 if (start == lo)
215 start++;
216 for ( ; start < hi; start++) {
217 Comparable pivot = (Comparable) a[start];
218
219 // Set left (and right) to the index where a[start] (pivot) belongs
220 int left = lo;
221 int right = start;
222 assert left <= right;
223 /*
224 * Invariants:
225 * pivot >= all in [lo, left).
226 * pivot < all in [right, start).
227 */
228 while (left < right) {
229 int mid = (left + right) >>> 1;
230 if (pivot.compareTo(a[mid]) < 0)
231 right = mid;
260 *
261 * A run is the longest ascending sequence with:
262 *
263 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
264 *
265 * or the longest descending sequence with:
266 *
267 * a[lo] > a[lo + 1] > a[lo + 2] > ...
268 *
269 * For its intended use in a stable mergesort, the strictness of the
270 * definition of "descending" is needed so that the call can safely
271 * reverse a descending sequence without violating stability.
272 *
273 * @param a the array in which a run is to be counted and possibly reversed
274 * @param lo index of the first element in the run
275 * @param hi index after the last element that may be contained in the run.
276 It is required that {@code lo < hi}.
277 * @return the length of the run beginning at the specified position in
278 * the specified array
279 */
280 @SuppressWarnings({"unchecked", "rawtypes"})
281 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
282 assert lo < hi;
283 int runHi = lo + 1;
284 if (runHi == hi)
285 return 1;
286
287 // Find end of run, and reverse range if descending
288 if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
289 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
290 runHi++;
291 reverseRange(a, lo, runHi);
292 } else { // Ascending
293 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
294 runHi++;
295 }
296
297 return runHi - lo;
298 }
299
300 /**
595 assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
596 return ofs;
597 }
598
599 /**
600 * Merges two adjacent runs in place, in a stable fashion. The first
601 * element of the first run must be greater than the first element of the
602 * second run (a[base1] > a[base2]), and the last element of the first run
603 * (a[base1 + len1-1]) must be greater than all elements of the second run.
604 *
605 * For performance, this method should be called only when len1 <= len2;
606 * its twin, mergeHi should be called if len1 >= len2. (Either method
607 * may be called if len1 == len2.)
608 *
609 * @param base1 index of first element in first run to be merged
610 * @param len1 length of first run to be merged (must be > 0)
611 * @param base2 index of first element in second run to be merged
612 * (must be aBase + aLen)
613 * @param len2 length of second run to be merged (must be > 0)
614 */
615 @SuppressWarnings({"unchecked", "rawtypes"})
616 private void mergeLo(int base1, int len1, int base2, int len2) {
617 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
618
619 // Copy first run into temp array
620 Object[] a = this.a; // For performance
621 Object[] tmp = ensureCapacity(len1);
622 System.arraycopy(a, base1, tmp, 0, len1);
623
624 int cursor1 = 0; // Indexes into tmp array
625 int cursor2 = base2; // Indexes int a
626 int dest = base1; // Indexes int a
627
628 // Move first element of second run and deal with degenerate cases
629 a[dest++] = a[cursor2++];
630 if (--len2 == 0) {
631 System.arraycopy(tmp, cursor1, a, dest, len1);
632 return;
633 }
634 if (len1 == 1) {
635 System.arraycopy(a, cursor2, a, dest, len2);
712 throw new IllegalArgumentException(
713 "Comparison method violates its general contract!");
714 } else {
715 assert len2 == 0;
716 assert len1 > 1;
717 System.arraycopy(tmp, cursor1, a, dest, len1);
718 }
719 }
720
721 /**
722 * Like mergeLo, except that this method should be called only if
723 * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
724 * may be called if len1 == len2.)
725 *
726 * @param base1 index of first element in first run to be merged
727 * @param len1 length of first run to be merged (must be > 0)
728 * @param base2 index of first element in second run to be merged
729 * (must be aBase + aLen)
730 * @param len2 length of second run to be merged (must be > 0)
731 */
732 @SuppressWarnings({"unchecked", "rawtypes"})
733 private void mergeHi(int base1, int len1, int base2, int len2) {
734 assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
735
736 // Copy second run into temp array
737 Object[] a = this.a; // For performance
738 Object[] tmp = ensureCapacity(len2);
739 System.arraycopy(a, base2, tmp, 0, len2);
740
741 int cursor1 = base1 + len1 - 1; // Indexes into a
742 int cursor2 = len2 - 1; // Indexes into tmp array
743 int dest = base2 + len2 - 1; // Indexes into a
744
745 // Move last element of first run and deal with degenerate cases
746 a[dest--] = a[cursor1--];
747 if (--len1 == 0) {
748 System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
749 return;
750 }
751 if (len2 == 1) {
752 dest -= len1;
|