FULL PRODUCT VERSION :
java version  " 1.7.0_07 " 
Java(TM) SE Runtime Environment (build 1.7.0_07-b10)
Java HotSpot(TM) Client VM (build 23.3-b01, mixed mode)


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

A DESCRIPTION OF THE PROBLEM :
The function mergeCollaps in the new TimSort algorithm does not preserve the invariant it should preserve, namely ALL i. runLen[i] > runLen[i+1]+runLen[i+2].   The problem is that after the pen-ultimate and the pen-pen-ultimate blocks are merged the invariant is not checked for runLen[stacksize-4]>runLen[stacksize-3]+runLen[stacksize-2].

The effect is that the sizes of the chunks do not have to grow according to the Fibonacci sequence as the author originally intended.  Therefore the runLen array may be too small to hold all the chunks.  The attached code will trigger this error. Admittedly, the chance that this bug happens by accident is very small, but it may lead to DenialOfService attacks.

As a bug fix, it would be enough to also check in mergeCollaps that runLen[stacksize-4]>runLen[stacksize-3]+runLen[stacksize-2] holds, and otherwise merge the last two blocks.  This way the invariant 1) will hold for all elements in the runLen array at the end of the method and invariant 2) follows from this (except for the last element where it is checked explicitly).  Both TimSort and ComparableTimSort have the same problem.

A different bug fix would be to allow more space in the runLen array in the constructor.  However, it is not easy to prove how much space would suffice with the current code.

REGRESSION.  Last worked in version 6u31

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the attached program

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: 19
        at java.util.ComparableTimSort.pushRun(ComparableTimSort.java:352)
        at java.util.ComparableTimSort.sort(ComparableTimSort.java:181)
        at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
        at java.util.Arrays.sort(Arrays.java:472)
        at BreakTimSort.run(BreakTimSort.java:68)
        at BreakTimSort.main(BreakTimSort.java:72)


REPRODUCIBILITY :
This bug can be reproduced always.

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

public class BreakTimSort {

    private static final int MIN=16;
    ArrayDeque<Integer> chunks = new ArrayDeque<Integer>();

    private static final int BOUND1 = 2*MIN+1;
    private static final int BOUND2 = BOUND1+MIN+2;
    private static final int BOUND3 = BOUND1+1+BOUND2;
    private static final int BOUND4 = BOUND2+1+BOUND3;
    private static final int BOUND5 = BOUND3+1+BOUND4;

    public int build(int size, int B) {
        chunks.addFirst(B);
        if (size < BOUND1) {
            chunks.addFirst(size);
            return size;
        }

        int asize = (size+2)/2;
        if (size >= BOUND2 && asize < BOUND1)
            asize = BOUND1;
        else if (size >= BOUND3 && asize < BOUND2)
            asize = BOUND2;
        else if (size >= BOUND4 && asize < BOUND3)
            asize = BOUND3;
        else if (size >= BOUND5 && asize < BOUND4)
            asize = BOUND4;
        if (size - asize >= B)
            throw new AssertionError( "  " +size+ " , " +asize+ " , " +B);
        return build (asize, size - asize);
    }

    public void run() {
        chunks.addFirst(MIN);

        int B = MIN+4;
        int A = B + MIN + 1;

        for (int i = 0; i< 8; i++) {
            int eps = build(A, B);
            B = B+A+1;
            A = B+eps + 1;
        }
        chunks.addFirst(B);
        chunks.addFirst(A);
        int total = 0;
        for (Integer len: chunks) {
            total += len;
        }
        int pow = MIN;
        while (pow < total)
            pow += pow;
        chunks.addLast(pow-total);
        System.err.println( " Total:  " +total);
        Object[] array = new Object[pow];
        int off = 0;
        int pos = 0;
        for (Integer len: chunks) {
            for (int i = 0; i < len; i++) {
                array[pos++] = Integer.valueOf(i == 0 ? 0 : 1);
            }
            off++;
        }
        Arrays.sort(array);
    }

    public static void main(String[] param) {
        new BreakTimSort().run();
    }
}

---------- END SOURCE ----------