// Arup Guha
// 2/24/2018
// Merge Sort written for Junior Knights - merge is written shorter here than mergesort.java

import java.util.*;

public class mergesort2 {

	final public static int N = 10000000;

	public static void main(String[] args) {

		// Generate a random array of size N.
		Random r = new Random();
		int[] vals = new int[N];
		for (int i=0; i<vals.length; i++)
			vals[i] = r.nextInt();

		// Show it's not sorted.
		System.out.println(isSorted(vals));

		// Call our Merge Sort.
		long start = System.currentTimeMillis();
		sort(vals, 0, vals.length-1);
		long end = System.currentTimeMillis();

		// Check if it's now sorted and print out how long it took.
		System.out.println(isSorted(vals));
		System.out.println("Sorted in "+(end-start)+" ms.");
	}

	// Returns true iff array is sorted.
	public static boolean isSorted(int[] array) {
		for (int i=0; i<array.length-1; i++)
			if (array[i] > array[i+1])
				return false;
		return true;
	}

	// Prints array - good to see what's going on in small cases.
	public static void print(int[] array) {
		for (int i=0; i<array.length; i++)
			System.out.print(array[i]+" ");
		System.out.println();
	}


	// Runs a merge sort on array[low..high]
	public static void sort(int[] array, int low, int high) {
		if (low < high) {

			int mid = (low+high)/2;

			// Sort left.
			sort(array, low, mid);

			// Sort right.
			sort(array, mid+1, high);

			// Merge together.
			merge(array, low, mid+1, high);
		}
	}

	// Merges array[sLeft..sRight-1] and array[sRight..eRight]
	public static void merge(int[] array, int sLeft, int sRight, int eRight) {

		// Array to copy in values.
		int[] tmp = new int[eRight-sLeft+1];
		int iLeft = sLeft, iRight = sRight;

		// Loop through iTmp
		for (int iTmp=0; iTmp < tmp.length; iTmp++) {

			// All cases where we take from left.
			if (iRight == eRight+1 || (iLeft < sRight && array[iLeft] < array[iRight])) {
				tmp[iTmp] = array[iLeft];
				iLeft++;
			}

			// Right value is smaller or only one we can take...
			else {
				tmp[iTmp] = array[iRight];
				iRight++;
			}
		}

		// Copy all values back.
		for (int i=0, j=sLeft; i<tmp.length; i++,j++)
			array[j] = tmp[i];
	}
}