TestTimSort.java

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 void runsCorrectWorstCase(int len) {
        long curr = minRun, prev=0;
        long runningTotal = len<minRun ? len : minRun;

        runs.add(runningTotal);
        
        while(runningTotal+prev+curr+1 <= len) {
            curr += prev+1;
            prev=curr-prev-1;
            runs.add(0, curr);
            runningTotal += curr;
        }
        
        runs.add(len-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);
    }

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