import java.util.Scanner;

public class MergeSort {
    private static int count1=0, count2 = 0;
    public static void print(int a[], int start, int stop)     {
        for (int i = start; i <= stop; i++)  {
            System.out.print (a[i] + "  ");
        }
        System.out.println();
    }

    public static void split (int a[], int low, int high)    {
        System.out.println ("Start of split(" + low + " , " + high + ")");
        if (low < high) {
            count1++;
            int middle1 = (low + high)/2;
            int middle2 = middle1 + 1;
            split(a, low, middle1);
            System.out.println("Partition Left : ");
            print(a, low, middle1);
            System.out.println();
            split (a, middle2, high);
            System.out.println("Partition Right : ");
            print(a, middle2, high);
            System.out.println();
            mergeSort(a, low, middle1, middle2, high);           
        }
        System.out.println ("End of split(" + low + " , " + high + ")");
    }

    public static void mergeSort (int a[], int left, int middle1, int middle2, int right)    {
        System.out.println ("left = " + left + " middle1 = " + middle1 + " right = " + right + " middle2 = " + middle2);
        int c[] = new int[a.length]; // creating/resetting the 'c' array for every iteration
        //Storing values of left and middle2 as local variables
        int cell1 = left; 
        int cell2 = middle2;
        int cell3 = left;
        while (cell1 <= middle1 && cell2 <= right){
            count2++;
            if (a[cell1] < a[cell2]){
                c[cell3] = a[cell1];
                cell1++;
                cell3++;
            }
            else{
                c[cell3] = a[cell2];
                cell2++;
                cell3++;
            }
        }
        if (cell1 == middle2){
            for (int i = cell2; i <=right; i++){
                count2++;
                c[cell3] = a[i];
                cell3++;
            }
        }
        else{
            for (int i = cell1; i <=middle1; i++){
                count2++;
                c[cell3] = a[i];
                cell3++;
            }
        }
        for (int i = left;  i <= right; i++) { // copying 'c' back to 'a'
            a[i] = c[i];
        }
        System.out.println ("Leaving Merge Sort :");
        print(a, left, right);
        System.out.println();
    }

    public static void main(String args[]) {
        int a[] = {12,1,0,9,56,29,45,85};
        System.out.print ("Starting Array: ");
        for (int i =0; i<a.length; i++)   {
            System.out.print(a[i] + " ");
        } 
        System.out.println();
        split (a, 0, a.length-1);
        System.out.println ("After Sorting -Merge Sort :");
        for (int i =0; i<a.length; i++)  { 
            System.out.print(a[i] + " ");
        } 
        System.out.println();  
        System.out.println ("Split = " + count1);
        System.out.println ("Merge = " + count2);

    }
}