PrintWorstCase.java

import java.util.Set;
import java.util.HashSet;

public class PrintWorstCase {
    private static final int MIN_MERGE = 32;
    private static final Set<Integer> WORST_CASE = new HashSet<Integer>();
    
    private static int minRun;

    public static void main(String[] args) {
        System.out.println(" Array size   Stack Size");
        for(int len=MIN_MERGE; len>0; len++) {
            int size = Math.max(JDKWorstCase(len), correctWorstCase(len));
            if(!WORST_CASE.contains(size)) {
                WORST_CASE.add(size);
                System.out.printf("%11d    %9d\n", len, size);
            }
        }
    }
    
    private static void setBound(long len) {
    	minRun = minRunLength(len);
    }

    private static int minRunLength(long 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 (int)n + r;
    }
    
    private static long first(long total) {
    	if(    (8*minRun+9 <= total)
    		|| (5*minRun+5 <= total && total <= 8*minRun+1)
    		|| (3*minRun+3 <= total && total <= 4*minRun+1)) {
    		return minRun+1;
    	}
    	while(total >= 2*minRun+1)
    		total=total/2+1;
    	return total;
    }
    
    public static int JDKWorstCase(long length) {
        setBound(length);
        int stackSize=0;
    	long runningTotal=0, curr=minRun+4, prev=minRun;
    	
    	while(runningTotal+curr+prev <= length) {
            runningTotal += prev + curr;
            stackSize +=2;
            long diff = first(prev);
    		prev = curr + diff + 1;
    		curr += prev + 1;
    	}
    	
    	if(runningTotal + prev <= length) {
            runningTotal += prev;
            stackSize++;
    	}
    	
    	if(runningTotal < length)
    	    stackSize++;
    	return stackSize;
    }

    public static int correctWorstCase(int length) {
        setBound(length);
        int stackSize=1;
        long curr = minRun, prev=0;
        long runningTotal = length<minRun ? length : minRun;
        
        while(runningTotal+prev+curr+1 <= length) {
            curr += prev+1;
            prev=curr-prev-1;
            runningTotal += curr;
            stackSize++;
        }
        
        if(runningTotal < length)
            stackSize++;
        return stackSize;
    }
}