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

Print this page




 190         assert lo == hi;
 191         ts.mergeForceCollapse();
 192         assert ts.stackSize == 1;
 193     }
 194 
 195     /**
 196      * Sorts the specified portion of the specified array using a binary
 197      * insertion sort.  This is the best method for sorting small numbers
 198      * of elements.  It requires O(n log n) compares, but O(n^2) data
 199      * movement (worst case).
 200      *
 201      * If the initial part of the specified range is already sorted,
 202      * this method can take advantage of it: the method assumes that the
 203      * elements from index {@code lo}, inclusive, to {@code start},
 204      * exclusive are already sorted.
 205      *
 206      * @param a the array in which a range is to be sorted
 207      * @param lo the index of the first element in the range to be sorted
 208      * @param hi the index after the last element in the range to be sorted
 209      * @param start the index of the first element in the range that is
 210      *        not already known to be sorted (@code lo <= start <= hi}
 211      */
 212     @SuppressWarnings("fallthrough")
 213     private static void binarySort(Object[] a, int lo, int hi, int start) {
 214         assert lo <= start && start <= hi;
 215         if (start == lo)
 216             start++;
 217         for ( ; start < hi; start++) {
 218             @SuppressWarnings("unchecked")
 219             Comparable<Object> pivot = (Comparable) a[start];
 220 
 221             // Set left (and right) to the index where a[start] (pivot) belongs
 222             int left = lo;
 223             int right = start;
 224             assert left <= right;
 225             /*
 226              * Invariants:
 227              *   pivot >= all in [lo, left).
 228              *   pivot <  all in [right, start).
 229              */
 230             while (left < right) {
 231                 int mid = (left + right) >>> 1;
 232                 if (pivot.compareTo(a[mid]) < 0)
 233                     right = mid;
 234                 else
 235                     left = mid + 1;
 236             }
 237             assert left == right;
 238 
 239             /*
 240              * The invariants still hold: pivot >= all in [lo, left) and
 241              * pivot < all in [left, start), so pivot belongs at left.  Note
 242              * that if there are elements equal to pivot, left points to the
 243              * first slot after them -- that's why this sort is stable.
 244              * Slide elements over to make room to make room for pivot.
 245              */
 246             int n = start - left;  // The number of elements to move
 247             // Switch is just an optimization for arraycopy in default case
 248             switch(n) {
 249                 case 2:  a[left + 2] = a[left + 1];
 250                 case 1:  a[left + 1] = a[left];
 251                          break;
 252                 default: System.arraycopy(a, left, a, left + 1, n);
 253             }
 254             a[left] = pivot;
 255         }
 256     }
 257 
 258     /**
 259      * Returns the length of the run beginning at the specified position in
 260      * the specified array and reverses the run if it is descending (ensuring
 261      * that the run will always be ascending when the method returns).
 262      *
 263      * A run is the longest ascending sequence with:
 264      *
 265      *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
 266      *
 267      * or the longest descending sequence with:
 268      *
 269      *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 270      *
 271      * For its intended use in a stable mergesort, the strictness of the
 272      * definition of "descending" is needed so that the call can safely
 273      * reverse a descending sequence without violating stability.
 274      *
 275      * @param a the array in which a run is to be counted and possibly reversed
 276      * @param lo index of the first element in the run
 277      * @param hi index after the last element that may be contained in the run.
 278               It is required that @code{lo < hi}.
 279      * @return  the length of the run beginning at the specified position in
 280      *          the specified array
 281      */
 282     @SuppressWarnings("unchecked")
 283     private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
 284         assert lo < hi;
 285         int runHi = lo + 1;
 286         if (runHi == hi)
 287             return 1;
 288 
 289         // Find end of run, and reverse range if descending
 290         if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
 291             while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
 292                 runHi++;
 293             reverseRange(a, lo, runHi);
 294         } else {                              // Ascending
 295             while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
 296                 runHi++;
 297         }
 298 
 299         return runHi - lo;
 300     }
 301 
 302     /**
 303      * Reverse the specified range of the specified array.
 304      *
 305      * @param a the array in which a range is to be reversed
 306      * @param lo the index of the first element in the range to be reversed
 307      * @param hi the index after the last element in the range to be reversed
 308      */
 309     private static void reverseRange(Object[] a, int lo, int hi) {
 310         hi--;
 311         while (lo < hi) {




 190         assert lo == hi;
 191         ts.mergeForceCollapse();
 192         assert ts.stackSize == 1;
 193     }
 194 
 195     /**
 196      * Sorts the specified portion of the specified array using a binary
 197      * insertion sort.  This is the best method for sorting small numbers
 198      * of elements.  It requires O(n log n) compares, but O(n^2) data
 199      * movement (worst case).
 200      *
 201      * If the initial part of the specified range is already sorted,
 202      * this method can take advantage of it: the method assumes that the
 203      * elements from index {@code lo}, inclusive, to {@code start},
 204      * exclusive are already sorted.
 205      *
 206      * @param a the array in which a range is to be sorted
 207      * @param lo the index of the first element in the range to be sorted
 208      * @param hi the index after the last element in the range to be sorted
 209      * @param start the index of the first element in the range that is
 210      *        not already known to be sorted ({@code lo <= start <= hi})
 211      */
 212     @SuppressWarnings("fallthrough")
 213     private static void binarySort(Object[] a, int lo, int hi, int start) {
 214         assert lo <= start && start <= hi;
 215         if (start == lo)
 216             start++;
 217         for ( ; start < hi; start++) {
 218             @SuppressWarnings("unchecked")
 219             Comparable<Object> pivot = (Comparable) a[start];
 220 
 221             // Set left (and right) to the index where a[start] (pivot) belongs
 222             int left = lo;
 223             int right = start;
 224             assert left <= right;
 225             /*
 226              * Invariants:
 227              *   pivot >= all in [lo, left).
 228              *   pivot <  all in [right, start).
 229              */
 230             while (left < right) {
 231                 int mid = (left + right) >>> 1;
 232                 if (pivot.compareTo(a[mid]) < 0)
 233                     right = mid;
 234                 else
 235                     left = mid + 1;
 236             }
 237             assert left == right;
 238 
 239             /*
 240              * The invariants still hold: pivot >= all in [lo, left) and
 241              * pivot < all in [left, start), so pivot belongs at left.  Note
 242              * that if there are elements equal to pivot, left points to the
 243              * first slot after them -- that's why this sort is stable.
 244              * Slide elements over to make room to make room for pivot.
 245              */
 246             int n = start - left;  // The number of elements to move
 247             // Switch is just an optimization for arraycopy in default case
 248             switch (n) {
 249                 case 2:  a[left + 2] = a[left + 1];
 250                 case 1:  a[left + 1] = a[left];
 251                          break;
 252                 default: System.arraycopy(a, left, a, left + 1, n);
 253             }
 254             a[left] = pivot;
 255         }
 256     }
 257 
 258     /**
 259      * Returns the length of the run beginning at the specified position in
 260      * the specified array and reverses the run if it is descending (ensuring
 261      * that the run will always be ascending when the method returns).
 262      *
 263      * A run is the longest ascending sequence with:
 264      *
 265      *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
 266      *
 267      * or the longest descending sequence with:
 268      *
 269      *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 270      *
 271      * For its intended use in a stable mergesort, the strictness of the
 272      * definition of "descending" is needed so that the call can safely
 273      * reverse a descending sequence without violating stability.
 274      *
 275      * @param a the array in which a run is to be counted and possibly reversed
 276      * @param lo index of the first element in the run
 277      * @param hi index after the last element that may be contained in the run.
 278               It is required that {@code lo < hi}.
 279      * @return  the length of the run beginning at the specified position in
 280      *          the specified array
 281      */
 282     @SuppressWarnings("unchecked")
 283     private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
 284         assert lo < hi;
 285         int runHi = lo + 1;
 286         if (runHi == hi)
 287             return 1;
 288 
 289         // Find end of run, and reverse range if descending
 290         if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
 291             while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
 292                 runHi++;
 293             reverseRange(a, lo, runHi);
 294         } else {                              // Ascending
 295             while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
 296                 runHi++;
 297         }
 298 
 299         return runHi - lo;
 300     }
 301 
 302     /**
 303      * Reverse the specified range of the specified array.
 304      *
 305      * @param a the array in which a range is to be reversed
 306      * @param lo the index of the first element in the range to be reversed
 307      * @param hi the index after the last element in the range to be reversed
 308      */
 309     private static void reverseRange(Object[] a, int lo, int hi) {
 310         hi--;
 311         while (lo < hi) {