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

(array) Review TimSort implementations

    Details

    • Type: Enhancement
    • Status: Open
    • Priority: P5
    • Resolution: Unresolved
    • Affects Version/s: 7u71, 8, 9
    • Fix Version/s: tbd
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Introduced In Version:
      7

      Description

       - 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);
              }
          }

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                lpriima Lev Priima
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Created:
                  Updated: