package mergeSort;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Arrays;


public class MS_external {
	@SuppressWarnings("resource")
	public static void main(String args[]) throws FileNotFoundException {

		System.out.println("Size of data; Time taken to sort (ms)");

		File fin = new File ("fileToSort.txt");
		Scanner stream = new Scanner(fin);

		for(int i = 100000; i <= 10000000; i+= 100000) {

			//create array, fill with data
			int[] sortMe = new int[i];
			for (int j = 0; j < sortMe.length; j++) {
				sortMe[j] = stream.nextInt();
			}

			//get time start
			long timeStart = System.currentTimeMillis();
			mergeSort(sortMe, sortMe.length);
			long timeEnd = System.currentTimeMillis();
			//calc time to sort
			long totalTime = timeEnd - timeStart;

			System.out.println(i + "; " + totalTime + "ms");

		}


	}

	public static void merge( int[] a, int[] l, int[] r, int leftSize, int rightSize) {

				//setup loop variables
			    int i = 0, j = 0, k = 0;

			    //sort while the bottom or top haven't been exhausted
			    while (i < leftSize && j < rightSize) {
			    	//if left el @i is less than right el @j
			        if (l[i] <= r[j]) {
			        	//update element for a
			            a[k] = l[i];
			            //increment pointers
			            k++;
			            i++;
			        }
			        else {
			        	//else use the other element
			            a[k] = r[j];
			            //increment pointers
			            k++;
			            j++;
			        }
			    }

			    //continue through all elements and add to a
			    while (i < leftSize) {
			        a[k] = l[i];
			        k++;
			        i++;
			    }

			    //continue through all elements and add to a
			    while (j < rightSize) {
			        a[k] = r[j];
			        k++;
			        j++;
			    }

			}

	public static void mergeSort(int[] a, int n) {


		//if there's one item, it's already sorted
	    if (n < 2) {
	        return;
	    }

	    //calculate the middle index from n/2
	    int middleIndex = n / 2;

	    //create new arrays for left and right, half and half
	    int[] l = new int[middleIndex];
	    int[] r = new int[n - middleIndex];

	    //copy first half of a into left array
	    for (int i = 0; i < middleIndex; i++) {
	        l[i] = a[i];
	    }
	    //copy second half of a into right array
	    for (int i = middleIndex; i < n; i++) {
	        r[i - middleIndex] = a[i];
	    }

	    //sort the left half
	    mergeSort(l, middleIndex);
	    //sort the right half
	    mergeSort(r, n - middleIndex);


	    //merge the arrays
	    merge(a, l, r, middleIndex, n - middleIndex);

	}
}