/*  Name: Chris Torrella
 *  COSC 311  FA19
 *  Final Project
 *  URL:
 */


package mergeSort;
//import java.util.Arrays;
import java.util.Random;


public class MS_Internal {
	public static void main(String args[]) {

		System.out.println("Size of data; Time taken to sort (ms)");
		Random r = new Random(97);

		int[][] MSEA = new int[100][2];

		for(int i = 100000; i <= 10000000; i+= 100000) {
			//go through datasets size 1 to 50

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

			//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");
			MSEA[(i / 100000) - 1][0] = i;
			MSEA[(i / 100000) - 1][1] = (int)totalTime;

		}

		float MSE = 0;

		for (int i = 0; i < 100; i++){
			MSE += Math.pow((MSEA[i][0] - MSEA[i][1]), 2);
		}

		MSE *= (1/100);

		System.out.println("MSE is " + MSE);


	}

	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);

	}
}