- 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 inJDK-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);
}
}
- evaluate performance {pro|re}gression from corrected mergeCollapse() method suggested in
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);
}
}
- is blocked by
-
JDK-8072909 TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
- Resolved