/**
 * Created by Linda Lawton on 6/29/2017.
 */
public class MergeSort {

    public static void main(String[] args) throws Exception {

        int[] data = new int[]{8, 3, 1, 7, 0};
        System.out.print("Before Sort: ");
        for (int i = 0; i < data.length; i++) System.out.print( data[i] + ",");
        System.out.println();
        sort(data,0,data.length-1);
        System.out.print("After Sort: ");
        for (int i = 0; i < data.length; i++) System.out.print( data[i] + ",");

    }

    public static void sort(int[] data, int start, int end) {

        if (end > start) {

            int middle = (start + end) / 2;
            sort(data, start, middle);
            sort(data, middle + 1, end);
            merge(data, start, middle, end);
        }
    }


    public static void merge(int[] data, int start, int mid, int end) {


        System.out.println("------------------------------------");
        System.out.println("Start: " + start + " Middle: " + mid + " End: " + end);
        System.out.print("Data is : " );
        for (int i = 0; i < data.length; i++) System.out.print( data[i] + ",");
        System.out.println();

        int[] temp = new int[data.length];

        int startOfLeft = start;
        int startOfRight = mid + 1;
        int pos = start;

        while (startOfLeft <= mid && startOfRight <= end) {

            if (data[startOfLeft] < data[startOfRight])
                temp[pos++] = data[startOfLeft++];
            else
                temp[pos++] = data[startOfRight++];
        }

        while (startOfLeft <= mid)
            temp[pos++] = data[startOfLeft++];

        while (startOfRight <= end) {
            temp[pos++] =  data[startOfRight++];
        }


        System.out.print("Temp is: ");
       for (int i = 0; i < data.length; i++)
           System.out.print( temp[i] + ",");

        int hold = (end-start) + 1;
        System.out.println();
        System.out.println("Hold is " + hold);
        for (int i = 0; i < hold; i++) {
            data[end] = temp[end];
            end--;
        }
        System.out.print("Data is : ");
        for (int i = 0; i < data.length; i++) System.out.print( data[i] + ",");
        System.out.println();
    }
}