FULL PRODUCT VERSION :
java version "1.7.0_75"
OpenJDK Runtime Environment (IcedTea 2.5.4) (7u75-2.5.4-1~precise1)
OpenJDK 64-Bit Server VM (build 24.75-b04, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Every OS, since this is portable Java code.

A DESCRIPTION OF THE PROBLEM :
As previously reported in bug 8011944, the function mergeCollapse in the TimSort class does not preserve the invariant runLen[i] > runLen[i+1]+runLen[i+2]. This leads to an ArrayIndexOutOfBoundsException in TimSort's pushRun method. We refer to 8011944 for more details.

The bug was marked as fixed, after an update in which the allocated length of runLen, as declared in the constructor, was increased. However, we found that the fix does not suffice, see the attached test case.
In particular, the declared length 40 of runLen which is chosen if the length of the input array is >= 119151, does not suffice.

We provide a full analysis of the bug in a paper, which is available at:
  http://envisage-project.eu/?page_id=1412

REGRESSION. Last worked in version 6u43

ADDITIONAL REGRESSION INFORMATION:
Last worked in version 6u31, according to bug report 8011944

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the attached test case as follows:
  java TestTimSort 67108864 (<=changed from paper to correct value)
or
  java -Xmx8G TestTimSort 1073741824

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
No Exception occurs during sorting.
ACTUAL -
ArrayIndexOutOfBoundsException

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 40
at java.util.TimSort.pushRun(TimSort.java:386)
at java.util.TimSort.sort(TimSort.java:213)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at TestTimSort.main(TestTimSort.java:18)


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;

public class TestTimSort {
    private static final int MIN_MERGE = 32;
    private static final Comparator<Object> NATURAL_ORDER =
        new Comparator<Object>() {
            @SuppressWarnings("unchecked")
            public int compare(Object first, Object second) {
                return ((Comparable<Object>)first).compareTo(second);
            }
        };
    
    private final int minRun;
private final List<Long> runs = new ArrayList<Long>();

    public static void main(String[] args) {
        int length = Integer.parseInt(args[0]);
        Arrays.sort(JDKWorstCase(length), NATURAL_ORDER);
    }
    
    private TestTimSort(int len) {
     minRun = minRunLength(len);
    }

    private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0; // Becomes 1 if any 1 bits are shifted off
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }
    
    /**
     * Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br>
     * 1. X = x_1 + ... + x_n <br>
     * 2. x_j >= minRun for all j <br>
     * 3. x_1 + ... + x_{j-2} < x_j < x_1 + ... + x_{j-1} for all j <br>
     * These conditions guarantee that TimSort merges all x_j's one by one
     * (resulting in X) using only merges on the second-to-last element.
     * @param X The sum of the sequence that should be added to runs.
     */
    private void generateJDKWrongElem(long X) {
     for(long newTotal; X >= 2*minRun+1; X = newTotal) {
     //Default strategy
     newTotal = X/2 + 1;
    
     //Specialized strategies
     if(3*minRun+3 <= X && X <= 4*minRun+1) {
     // add x_1=MIN+1, x_2=MIN, x_3=X-newTotal to runs
     newTotal = 2*minRun+1;
     } else if(5*minRun+5 <= X && X <= 6*minRun+5) {
     // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal to runs
     newTotal = 3*minRun+3;
     } else if(8*minRun+9 <= X && X <= 10*minRun+9) {
     // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal to runs
     newTotal = 5*minRun+5;
     } else if(13*minRun+15 <= X && X <= 16*minRun+17) {
     // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal to runs
     newTotal = 8*minRun+9;
     }
     runs.add(0, X-newTotal);
     }
     runs.add(0, X);
    }

    /**
     * Fills <code>runs</code> with a sequence of run lengths of the form<br>
     * Y_n x_{n,1} x_{n,2} ... x_{n,l_n} <br>
     * Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br>
     * ... <br>
     * Y_1 x_{1,1} x_{1,2} ... x_{1,l_1}<br>
     * The Y_i's are chosen to satisfy the invariant throughout execution,
     * but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>)
     * into an X_i that violates the invariant.
     * @param X The sum of all run lengths that will be added to <code>runs</code>.
     */
    private void runsJDKWorstCase(int length) {
     long runningTotal = 0, Y=minRun+4, X=minRun;
    
     while(runningTotal+Y+X <= length) {
            runningTotal += X + Y;
            generateJDKWrongElem(X);
     runs.add(0,Y);
    
     // X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1}
     X = Y + runs.get(1) + 1;
    
     // Y_{i+1} = X_{i+1} + Y_i + 1
     Y += X + 1;
     }
    
     if(runningTotal + X <= length) {
            runningTotal += X;
            generateJDKWrongElem(X);
     }
    
     runs.add(length-runningTotal);
    }

    private Integer[] createArray(int length) {
        Integer[] a = new Integer[length];
        Arrays.fill(a, 0);
        int endRun = -1;
        for(long len : runs)
            a[endRun+=len] = 1;
        a[length-1]=0;
        
        return a;
    }

    public static Integer[] JDKWorstCase(int length) {
        TestTimSort t = new TestTimSort(length);
        t.runsJDKWorstCase(length);
        return t.createArray(length);
    }

}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
There are two options:
 1. In the constructor of the TimSort class, change
        int stackLen = (len < 120 ? 5 :
                        len < 1542 ? 10 :
                        len < 119151 ? 24 : 40);
to

        int stackLen = (len < 120 ? 5 :
                        len < 1542 ? 10 :
                        len < 119151 ? 24 : 49);

 2. Change the mergeCollapse method of TimSort to:
    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);
        }
    }