import java.util.*;

public class SortingDemo {

    public static void insertionSort(int[] a) {
        insertionSort(a,0,a.length-1);
    }

    private static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo+1; i <= hi; i++) {
            int j = i; // invariant: everything <i is in sorted order
            int tmp = a[i];
            while ((j > lo) && (a[j-1] > tmp)) { // until at the correct place
                a[j] = a[j-1]; // shift one to the right
                j--;  // walk backward
            }
            a[j] = tmp;  // insert into sorted order
        }
    }

    private static void mergeSort(int[] a, int lo, int hi, int[] work) {
        if (lo >= hi)
            return;                 // a[lo] is sorted already

        int mid = (lo+hi)/2;
        mergeSort(a,lo,mid,work);      // Sort sublist a[lo..mid]
        mergeSort(a,mid+1,hi,work);    // Sort sublist a[mid+1..hi]

        int t_lo = lo, t_hi = mid+1;
        for (int k = lo; k <= hi; k++)            // Merge sorted sublists
            if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi])))
                work[k] = a[t_lo++];
            else
                work[k] = a[t_hi++];
        for (int k = lo; k <= hi; k++)  // Copy work back to a
            a[k] = work[k];
    }

    private static void smartMergeSort(int[] a, int lo, int hi, int[] work, int stopsize) {
        if (hi-lo <= stopsize) {
            insertionSort(a,lo,hi); // insertSort is faster here
            return;
        }
        int mid = (lo+hi)/2;
        smartMergeSort(a,lo,mid,work,stopsize); // lower half
        smartMergeSort(a,mid+1,hi,work,stopsize); // upper half

        int t_lo = lo, t_hi = mid+1;
        for (int k = lo; k <= hi; k++)            // Merge sorted sublists
            if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi])))
                work[k] = a[t_lo++];
            else
                work[k] = a[t_hi++];
        for (int k = lo; k <= hi; k++)
            a[k] = work[k]; // Copy work back to a
    }

    public static void mergeSort(int[] a) {
        int[] work = new int[a.length];
        mergeSort(a,0,a.length-1,work);
    }

    public static void smartMergeSort(int[] a, int stopsize) {
        int[] work = new int[a.length];
        smartMergeSort(a,0,a.length-1,work, stopsize);
    }

	public static void insertMergeCompare(int size) {
        int[] a = new int[size];
        int[] b,c;
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt(1<<30);
        b = (int[])a.clone();
        long t1=System.currentTimeMillis();
        insertionSort(a);
        long t2=System.currentTimeMillis();
        mergeSort(b);
        long t3=System.currentTimeMillis();
        System.out.println("size="+size+"   InsertSort: " + (t2-t1) + ", MergeSort: " + (t3-t2));
	}

	public static void smartMergeCompare(int base) {
        int[] a = new int[1<<20];
        int[] b,c;
        long tt1=0, tt2=0;
        Random r = new Random();
        for(int k=0;k<10;k++) {
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt(1<<30);
        b = (int[])a.clone();
        c = (int[])a.clone();
        Arrays.sort(c);
        long t1=System.currentTimeMillis();
        mergeSort(b);
        long t2=System.currentTimeMillis();
        tt1+=t2-t1;
        smartMergeSort(a,base);
        long t3=System.currentTimeMillis();
        tt2+=t3-t2;
		}
//        if (!Arrays.equals(a,b)) throw new RuntimeException("sort bug");
//        if (!Arrays.equals(a,c)) throw new RuntimeException("sort bug");
        System.out.println("base="+base+"   Merge: " + (tt1) + ", SmartMerge: " + (tt2));

	}

    public static void main(String[] args) {
		insertMergeCompare(1000);
		insertMergeCompare(2000);
		insertMergeCompare(4000);
		insertMergeCompare(8000);
		insertMergeCompare(16000);
		insertMergeCompare(32000);
		insertMergeCompare(64000);
		insertMergeCompare(128000);
		insertMergeCompare(256000);
		insertMergeCompare(512000);
		insertMergeCompare(1024000);
/*		smartMergeCompare(2);
		smartMergeCompare(4);
		smartMergeCompare(8);
		smartMergeCompare(16);
		smartMergeCompare(32);
		smartMergeCompare(64);
		smartMergeCompare(128);
		smartMergeCompare(256);
		smartMergeCompare(512);
		smartMergeCompare(1024);
		smartMergeCompare(2048);
*/    }
}