import java.util.Arrays;
import java.util.Random;

/**
 * Created by Matthew Gilliard
 * Date: 10/07/11
 * Time: 18:22
 */
public class SortedRespectDue {

    public static void main(String... args) {

        Random r = new Random();

        int[] maxThresholds = {2, 3, 5, 7, 10, 15, 20, 25, 35, 50, 75, 150, 300, 600};

        System.out.print("size");
        for (int k : maxThresholds) {
            System.out.print(", T=" + k);
        }
        System.out.println();

        for (double d = 1; d < 10000000; d *= 1.1) {

            int i = (int) d;

            Long[] array = new Long[i];

            for (int j = 0; j < i; j++) {
                array[j] = r.nextLong();
            }

            System.out.print(i);
            for (int k : maxThresholds) {

                Long[] sortMe = new Long[i];
                System.arraycopy(array, 0, sortMe, 0, i);

                long start = System.currentTimeMillis();
                sort(sortMe, k);
                System.out.print(", " + (System.currentTimeMillis() - start));
            }
            System.out.println();

        }

    }

    public static void sort(Object[] a, int threshold) {
        Object[] aux = (Object[]) a.clone();
        mergeSort(aux, a, 0, a.length, 0, threshold);
    }

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off,
                                  int threshold) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < threshold) {
            for (int i = low; i < high; i++)
                for (int j = i; j > low &&
                        ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, threshold);
        mergeSort(dest, src, mid, high, -off, threshold);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

}