Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8074149

(array) Review TimSort implementations

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P5 P5
    • tbd
    • 7u71, 8, 9
    • core-libs
    • 7

       - review and remove duplicate code from TimSort: merge java/util/ComparableTimSort.java and java/util/TimSort.java
       - evaluate performance {pro|re}gression from corrected mergeCollapse() method suggested in JDK-8072909 and possibly apply it:
      private void mergeCollapse() {
              while (stackSize > 1) {
                  int n = stackSize - 2;
                  if ( n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]
                      || n-1 > 0 && runLen[n-2] <= runLen[n] + runLen[n-1]) {
                      if (runLen[n - 1] < runLen[n + 1])
                          n--;
                  } else if (n<0 || runLen[n] > runLen[n + 1]) {
                      break; // Invariant is established
                  }
                  mergeAt(n);
              }
          }

            Unassigned Unassigned
            lpriima Lev Priima
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

              Created:
              Updated: