src/share/classes/java/util/TimSort.java

Print this page




 222         assert lo == hi;
 223         ts.mergeForceCollapse();
 224         assert ts.stackSize == 1;
 225     }
 226 
 227     /**
 228      * Sorts the specified portion of the specified array using a binary
 229      * insertion sort.  This is the best method for sorting small numbers
 230      * of elements.  It requires O(n log n) compares, but O(n^2) data
 231      * movement (worst case).
 232      *
 233      * If the initial part of the specified range is already sorted,
 234      * this method can take advantage of it: the method assumes that the
 235      * elements from index {@code lo}, inclusive, to {@code start},
 236      * exclusive are already sorted.
 237      *
 238      * @param a the array in which a range is to be sorted
 239      * @param lo the index of the first element in the range to be sorted
 240      * @param hi the index after the last element in the range to be sorted
 241      * @param start the index of the first element in the range that is
 242      *        not already known to be sorted (@code lo <= start <= hi}
 243      * @param c comparator to used for the sort
 244      */
 245     @SuppressWarnings("fallthrough")
 246     private static <T> void binarySort(T[] a, int lo, int hi, int start,
 247                                        Comparator<? super T> c) {
 248         assert lo <= start && start <= hi;
 249         if (start == lo)
 250             start++;
 251         for ( ; start < hi; start++) {
 252             T pivot = a[start];
 253 
 254             // Set left (and right) to the index where a[start] (pivot) belongs
 255             int left = lo;
 256             int right = start;
 257             assert left <= right;
 258             /*
 259              * Invariants:
 260              *   pivot >= all in [lo, left).
 261              *   pivot <  all in [right, start).
 262              */
 263             while (left < right) {
 264                 int mid = (left + right) >>> 1;
 265                 if (c.compare(pivot, a[mid]) < 0)
 266                     right = mid;
 267                 else
 268                     left = mid + 1;
 269             }
 270             assert left == right;
 271 
 272             /*
 273              * The invariants still hold: pivot >= all in [lo, left) and
 274              * pivot < all in [left, start), so pivot belongs at left.  Note
 275              * that if there are elements equal to pivot, left points to the
 276              * first slot after them -- that's why this sort is stable.
 277              * Slide elements over to make room to make room for pivot.
 278              */
 279             int n = start - left;  // The number of elements to move
 280             // Switch is just an optimization for arraycopy in default case
 281             switch(n) {
 282                 case 2:  a[left + 2] = a[left + 1];
 283                 case 1:  a[left + 1] = a[left];
 284                          break;
 285                 default: System.arraycopy(a, left, a, left + 1, n);
 286             }
 287             a[left] = pivot;
 288         }
 289     }
 290 
 291     /**
 292      * Returns the length of the run beginning at the specified position in
 293      * the specified array and reverses the run if it is descending (ensuring
 294      * that the run will always be ascending when the method returns).
 295      *
 296      * A run is the longest ascending sequence with:
 297      *
 298      *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
 299      *
 300      * or the longest descending sequence with:
 301      *
 302      *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 303      *
 304      * For its intended use in a stable mergesort, the strictness of the
 305      * definition of "descending" is needed so that the call can safely
 306      * reverse a descending sequence without violating stability.
 307      *
 308      * @param a the array in which a run is to be counted and possibly reversed
 309      * @param lo index of the first element in the run
 310      * @param hi index after the last element that may be contained in the run.
 311               It is required that @code{lo < hi}.
 312      * @param c the comparator to used for the sort
 313      * @return  the length of the run beginning at the specified position in
 314      *          the specified array
 315      */
 316     private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
 317                                                     Comparator<? super T> c) {
 318         assert lo < hi;
 319         int runHi = lo + 1;
 320         if (runHi == hi)
 321             return 1;
 322 
 323         // Find end of run, and reverse range if descending
 324         if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
 325             while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
 326                 runHi++;
 327             reverseRange(a, lo, runHi);
 328         } else {                              // Ascending
 329             while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
 330                 runHi++;
 331         }
 332 
 333         return runHi - lo;
 334     }
 335 
 336     /**
 337      * Reverse the specified range of the specified array.
 338      *
 339      * @param a the array in which a range is to be reversed
 340      * @param lo the index of the first element in the range to be reversed
 341      * @param hi the index after the last element in the range to be reversed
 342      */
 343     private static void reverseRange(Object[] a, int lo, int hi) {
 344         hi--;
 345         while (lo < hi) {




 222         assert lo == hi;
 223         ts.mergeForceCollapse();
 224         assert ts.stackSize == 1;
 225     }
 226 
 227     /**
 228      * Sorts the specified portion of the specified array using a binary
 229      * insertion sort.  This is the best method for sorting small numbers
 230      * of elements.  It requires O(n log n) compares, but O(n^2) data
 231      * movement (worst case).
 232      *
 233      * If the initial part of the specified range is already sorted,
 234      * this method can take advantage of it: the method assumes that the
 235      * elements from index {@code lo}, inclusive, to {@code start},
 236      * exclusive are already sorted.
 237      *
 238      * @param a the array in which a range is to be sorted
 239      * @param lo the index of the first element in the range to be sorted
 240      * @param hi the index after the last element in the range to be sorted
 241      * @param start the index of the first element in the range that is
 242      *        not already known to be sorted ({@code lo <= start <= hi})
 243      * @param c comparator to used for the sort
 244      */
 245     @SuppressWarnings("fallthrough")
 246     private static <T> void binarySort(T[] a, int lo, int hi, int start,
 247                                        Comparator<? super T> c) {
 248         assert lo <= start && start <= hi;
 249         if (start == lo)
 250             start++;
 251         for ( ; start < hi; start++) {
 252             T pivot = a[start];
 253 
 254             // Set left (and right) to the index where a[start] (pivot) belongs
 255             int left = lo;
 256             int right = start;
 257             assert left <= right;
 258             /*
 259              * Invariants:
 260              *   pivot >= all in [lo, left).
 261              *   pivot <  all in [right, start).
 262              */
 263             while (left < right) {
 264                 int mid = (left + right) >>> 1;
 265                 if (c.compare(pivot, a[mid]) < 0)
 266                     right = mid;
 267                 else
 268                     left = mid + 1;
 269             }
 270             assert left == right;
 271 
 272             /*
 273              * The invariants still hold: pivot >= all in [lo, left) and
 274              * pivot < all in [left, start), so pivot belongs at left.  Note
 275              * that if there are elements equal to pivot, left points to the
 276              * first slot after them -- that's why this sort is stable.
 277              * Slide elements over to make room to make room for pivot.
 278              */
 279             int n = start - left;  // The number of elements to move
 280             // Switch is just an optimization for arraycopy in default case
 281             switch (n) {
 282                 case 2:  a[left + 2] = a[left + 1];
 283                 case 1:  a[left + 1] = a[left];
 284                          break;
 285                 default: System.arraycopy(a, left, a, left + 1, n);
 286             }
 287             a[left] = pivot;
 288         }
 289     }
 290 
 291     /**
 292      * Returns the length of the run beginning at the specified position in
 293      * the specified array and reverses the run if it is descending (ensuring
 294      * that the run will always be ascending when the method returns).
 295      *
 296      * A run is the longest ascending sequence with:
 297      *
 298      *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
 299      *
 300      * or the longest descending sequence with:
 301      *
 302      *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 303      *
 304      * For its intended use in a stable mergesort, the strictness of the
 305      * definition of "descending" is needed so that the call can safely
 306      * reverse a descending sequence without violating stability.
 307      *
 308      * @param a the array in which a run is to be counted and possibly reversed
 309      * @param lo index of the first element in the run
 310      * @param hi index after the last element that may be contained in the run.
 311               It is required that {@code lo < hi}.
 312      * @param c the comparator to used for the sort
 313      * @return  the length of the run beginning at the specified position in
 314      *          the specified array
 315      */
 316     private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
 317                                                     Comparator<? super T> c) {
 318         assert lo < hi;
 319         int runHi = lo + 1;
 320         if (runHi == hi)
 321             return 1;
 322 
 323         // Find end of run, and reverse range if descending
 324         if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
 325             while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
 326                 runHi++;
 327             reverseRange(a, lo, runHi);
 328         } else {                              // Ascending
 329             while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
 330                 runHi++;
 331         }
 332 
 333         return runHi - lo;
 334     }
 335 
 336     /**
 337      * Reverse the specified range of the specified array.
 338      *
 339      * @param a the array in which a range is to be reversed
 340      * @param lo the index of the first element in the range to be reversed
 341      * @param hi the index after the last element in the range to be reversed
 342      */
 343     private static void reverseRange(Object[] a, int lo, int hi) {
 344         hi--;
 345         while (lo < hi) {