@@ -0,0 +1,2360 @@
+import java.util.Set;%0Aimport java.util.HashSet;%0A%0Apublic class PrintWorstCase %7B%0A    private static final int MIN_MERGE = 32;%0A    private static final Set%3CInteger%3E WORST_CASE = new HashSet%3CInteger%3E();%0A    %0A    private static int minRun;%0A%0A    public static void main(String%5B%5D args) %7B%0A        System.out.println(%22 Array size   Stack Size%22);%0A        for(int len=MIN_MERGE; len%3E0; len++) %7B%0A            int size = Math.max(JDKWorstCase(len), correctWorstCase(len));%0A            if(!WORST_CASE.contains(size)) %7B%0A                WORST_CASE.add(size);%0A                System.out.printf(%22%2511d    %259d%5Cn%22, len, size);%0A            %7D%0A        %7D%0A    %7D%0A    %0A    private static void setBound(long len) %7B%0A    %09minRun = minRunLength(len);%0A    %7D%0A%0A    private static int minRunLength(long n) %7B%0A        assert n %3E= 0;%0A        int r = 0;      // Becomes 1 if any 1 bits are shifted off%0A        while (n %3E= MIN_MERGE) %7B%0A            r %7C= (n & 1);%0A            n %3E%3E= 1;%0A        %7D%0A        return (int)n + r;%0A    %7D%0A    %0A    private static long first(long total) %7B%0A    %09if(    (8*minRun+9 %3C= total)%0A    %09%09%7C%7C (5*minRun+5 %3C= total && total %3C= 8*minRun+1)%0A    %09%09%7C%7C (3*minRun+3 %3C= total && total %3C= 4*minRun+1)) %7B%0A    %09%09return minRun+1;%0A    %09%7D%0A    %09while(total %3E= 2*minRun+1)%0A    %09%09total=total/2+1;%0A    %09return total;%0A    %7D%0A    %0A    public static int JDKWorstCase(long length) %7B%0A        setBound(length);%0A        int stackSize=0;%0A    %09long runningTotal=0, curr=minRun+4, prev=minRun;%0A    %09%0A    %09while(runningTotal+curr+prev %3C= length) %7B%0A            runningTotal += prev + curr;%0A            stackSize +=2;%0A            long diff = first(prev);%0A    %09%09prev = curr + diff + 1;%0A    %09%09curr += prev + 1;%0A    %09%7D%0A    %09%0A    %09if(runningTotal + prev %3C= length) %7B%0A            runningTotal += prev;%0A            stackSize++;%0A    %09%7D%0A    %09%0A    %09if(runningTotal %3C length)%0A    %09    stackSize++;%0A    %09return stackSize;%0A    %7D%0A%0A    public static int correctWorstCase(int length) %7B%0A        setBound(length);%0A        int stackSize=1;%0A        long curr = minRun, prev=0;%0A        long runningTotal = length%3CminRun ? length : minRun;%0A        %0A        while(runningTotal+prev+curr+1 %3C= length) %7B%0A            curr += prev+1;%0A            prev=curr-prev-1;%0A            runningTotal += curr;%0A            stackSize++;%0A        %7D%0A        %0A        if(runningTotal %3C length)%0A            stackSize++;%0A        return stackSize;%0A    %7D%0A%7D%0A

Add PrintWorstCase.java