Print this page


Split Close
Expand all
Collapse all
          --- old/src/share/classes/java/util/TimSort.java
          +++ new/src/share/classes/java/util/TimSort.java
↓ open down ↓ 231 lines elided ↑ open up ↑
 232  232       *
 233  233       * If the initial part of the specified range is already sorted,
 234  234       * this method can take advantage of it: the method assumes that the
 235  235       * elements from index {@code lo}, inclusive, to {@code start},
 236  236       * exclusive are already sorted.
 237  237       *
 238  238       * @param a the array in which a range is to be sorted
 239  239       * @param lo the index of the first element in the range to be sorted
 240  240       * @param hi the index after the last element in the range to be sorted
 241  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}
      242 +     *        not already known to be sorted ({@code lo <= start <= hi})
 243  243       * @param c comparator to used for the sort
 244  244       */
 245  245      @SuppressWarnings("fallthrough")
 246  246      private static <T> void binarySort(T[] a, int lo, int hi, int start,
 247  247                                         Comparator<? super T> c) {
 248  248          assert lo <= start && start <= hi;
 249  249          if (start == lo)
 250  250              start++;
 251  251          for ( ; start < hi; start++) {
 252  252              T pivot = a[start];
↓ open down ↓ 18 lines elided ↑ open up ↑
 271  271  
 272  272              /*
 273  273               * The invariants still hold: pivot >= all in [lo, left) and
 274  274               * pivot < all in [left, start), so pivot belongs at left.  Note
 275  275               * that if there are elements equal to pivot, left points to the
 276  276               * first slot after them -- that's why this sort is stable.
 277  277               * Slide elements over to make room to make room for pivot.
 278  278               */
 279  279              int n = start - left;  // The number of elements to move
 280  280              // Switch is just an optimization for arraycopy in default case
 281      -            switch(n) {
      281 +            switch (n) {
 282  282                  case 2:  a[left + 2] = a[left + 1];
 283  283                  case 1:  a[left + 1] = a[left];
 284  284                           break;
 285  285                  default: System.arraycopy(a, left, a, left + 1, n);
 286  286              }
 287  287              a[left] = pivot;
 288  288          }
 289  289      }
 290  290  
 291  291      /**
↓ open down ↓ 9 lines elided ↑ open up ↑
 301  301       *
 302  302       *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
 303  303       *
 304  304       * For its intended use in a stable mergesort, the strictness of the
 305  305       * definition of "descending" is needed so that the call can safely
 306  306       * reverse a descending sequence without violating stability.
 307  307       *
 308  308       * @param a the array in which a run is to be counted and possibly reversed
 309  309       * @param lo index of the first element in the run
 310  310       * @param hi index after the last element that may be contained in the run.
 311      -              It is required that @code{lo < hi}.
      311 +              It is required that {@code lo < hi}.
 312  312       * @param c the comparator to used for the sort
 313  313       * @return  the length of the run beginning at the specified position in
 314  314       *          the specified array
 315  315       */
 316  316      private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
 317  317                                                      Comparator<? super T> c) {
 318  318          assert lo < hi;
 319  319          int runHi = lo + 1;
 320  320          if (runHi == hi)
 321  321              return 1;
 322  322  
 323  323          // Find end of run, and reverse range if descending
 324  324          if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
 325      -            while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
      325 +            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
 326  326                  runHi++;
 327  327              reverseRange(a, lo, runHi);
 328  328          } else {                              // Ascending
 329  329              while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
 330  330                  runHi++;
 331  331          }
 332  332  
 333  333          return runHi - lo;
 334  334      }
 335  335  
↓ open down ↓ 593 lines elided ↑ open up ↑
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX