## src/share/classes/java/util/ComparableTimSort.java

 ``` `````` 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; ```