import java.util.Random;

public class sort {
	private static int numberOfValues = 1000;
	private static int[] sortArr = new int[numberOfValues];
	private static Random rand = new Random();
	public static void main(String[] args) {
		getArr(numberOfValues, sortArr);
		long start = System.currentTimeMillis();
		insertionSort(numberOfValues, sortArr);

		long end = System.currentTimeMillis();
		System.out.println("Merge took: " + (end - start) + "milliseconds");

		for(int i = 0; i < numberOfValues; i++) {
			System.out.println(sortArr[i] + " ");

		}
	}

	public static int[] insertionSort(int b, int[] a) {
		for(int i = 0; i < numberOfValues; i++) {
			int x = a[i];
			int k = i - 1;

			while(k >= 0 && a[k] > x) {
				a[k + 1] = a[k];
				k = k - 1;
			}
			a[k + 1]= x;
		}
		return a;
	}

	public static int[] getArr(int a, int[] b) {
		for(int i = 0; i < numberOfValues; i++) {
			sortArr[i] = rand.nextInt(101);
		}
		return sortArr;
	}

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

	private static void mergeSort(int [] a, int [] tmp, int left, int right)
	{
		if( left < right )
		{
			int center = (left + right) / 2;
			mergeSort(a, tmp, left, center);
			mergeSort(a, tmp, center + 1, right);
			merge(a, tmp, left, center + 1, right);
		}
	}

	private static void merge(int[] a, int[] tmp, int left, int right, int rightEnd )
    {
        int leftEnd = right - 1;
        int k = left;
        int num = rightEnd - left + 1;

        while(left <= leftEnd && right <= rightEnd)
            if(a[left] <= (a[right]))
                tmp[k++] = a[left++];
            else
                tmp[k++] = a[right++];

        while(left <= leftEnd)    // Copy rest of first half
            tmp[k++] = a[left++];

        while(right <= rightEnd)  // Copy rest of right half
            tmp[k++] = a[right++];

        // Copy tmp back
        for(int i = 0; i < num; i++, rightEnd--)
            a[rightEnd] = tmp[rightEnd];
    }

}