Print this page


Split Close
Expand all
Collapse all
          --- old/src/share/classes/java/util/ComparableTimSort.java
          +++ new/src/share/classes/java/util/ComparableTimSort.java
↓ open down ↓ 199 lines elided ↑ open up ↑
 200  200       *
 201  201       * If the initial part of the specified range is already sorted,
 202  202       * this method can take advantage of it: the method assumes that the
 203  203       * elements from index {@code lo}, inclusive, to {@code start},
 204  204       * exclusive are already sorted.
 205  205       *
 206  206       * @param a the array in which a range is to be sorted
 207  207       * @param lo the index of the first element in the range to be sorted
 208  208       * @param hi the index after the last element in the range to be sorted
 209  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}
      210 +     *        not already known to be sorted ({@code lo <= start <= hi})
 211  211       */
 212  212      @SuppressWarnings("fallthrough")
 213  213      private static void binarySort(Object[] a, int lo, int hi, int start) {
 214  214          assert lo <= start && start <= hi;
 215  215          if (start == lo)
 216  216              start++;
 217  217          for ( ; start < hi; start++) {
 218  218              @SuppressWarnings("unchecked")
 219  219              Comparable<Object> pivot = (Comparable) a[start];
 220  220  
↓ open down ↓ 17 lines elided ↑ open up ↑
 238  238  
 239  239              /*
 240  240               * The invariants still hold: pivot >= all in [lo, left) and
 241  241               * pivot < all in [left, start), so pivot belongs at left.  Note
 242  242               * that if there are elements equal to pivot, left points to the
 243  243               * first slot after them -- that's why this sort is stable.
 244  244               * Slide elements over to make room to make room for pivot.
 245  245               */
 246  246              int n = start - left;  // The number of elements to move
 247  247              // Switch is just an optimization for arraycopy in default case
 248      -            switch(n) {
      248 +            switch (n) {
 249  249                  case 2:  a[left + 2] = a[left + 1];
 250  250                  case 1:  a[left + 1] = a[left];
 251  251                           break;
 252  252                  default: System.arraycopy(a, left, a, left + 1, n);
 253  253              }
 254  254              a[left] = pivot;
 255  255          }
 256  256      }
 257  257  
 258  258      /**
↓ open down ↓ 9 lines elided ↑ open up ↑
 268  268       *
 269  269       *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 270  270       *
 271  271       * For its intended use in a stable mergesort, the strictness of the
 272  272       * definition of "descending" is needed so that the call can safely
 273  273       * reverse a descending sequence without violating stability.
 274  274       *
 275  275       * @param a the array in which a run is to be counted and possibly reversed
 276  276       * @param lo index of the first element in the run
 277  277       * @param hi index after the last element that may be contained in the run.
 278      -              It is required that @code{lo < hi}.
      278 +              It is required that {@code lo < hi}.
 279  279       * @return  the length of the run beginning at the specified position in
 280  280       *          the specified array
 281  281       */
 282  282      @SuppressWarnings("unchecked")
 283  283      private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
 284  284          assert lo < hi;
 285  285          int runHi = lo + 1;
 286  286          if (runHi == hi)
 287  287              return 1;
 288  288  
 289  289          // Find end of run, and reverse range if descending
 290  290          if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
 291      -            while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
      291 +            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
 292  292                  runHi++;
 293  293              reverseRange(a, lo, runHi);
 294  294          } else {                              // Ascending
 295  295              while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
 296  296                  runHi++;
 297  297          }
 298  298  
 299  299          return runHi - lo;
 300  300      }
 301  301  
↓ open down ↓ 594 lines elided ↑ open up ↑
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX