JDK-8074149 : (array) Review TimSort implementations
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 7u71,8,9
  • Priority: P5
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2015-03-02
  • Updated: 2018-09-20
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other
tbdUnresolved
Related Reports
Blocks :  
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); 
        } 
    }