import java.util.Arrays;

public class MergeSort_Algo {
    public static void main(String[] args)
    {
        int[] ary = new int[]{20, 9, 3, 10, 300, 201, 11, 100 };

        int[] result = mergeSort(ary);
        printArray(result);
    }

    private static int[] mergeSort(int[] ary) {
        if (ary.length == 1) return ary;
        int[] aryLeft = mergeSort(subArray(ary, 0, ary.length/2)); // split is done here in the input
        int[] aryRight = mergeSort(subArray(ary, ary.length/2, ary.length)); // split is done here in the input
        return merge(aryLeft, aryRight);
    }

    // imagine you are at the last step of mergesort when you are coming from the bottom up.
    // Therefore, the array with size 1 is sorted; then up and the arrays with size 2 will be sorted too.
    // Here, we are simulating a up-k layers, and now we have two sorted sub-arrays to be merged.
    private static int[] merge(int[] aryLeftSorted, int[] aryRightSorted){
        if (aryLeftSorted.length == 0) return aryRightSorted;
        if (aryRightSorted.length == 0) return aryLeftSorted;

        int[] result = null;
        if (aryLeftSorted[0] <= aryRightSorted[0]) { // if smaller, extract it out in this layer
            result = concat(subArray(aryLeftSorted, 0, 1) , merge(subArray(aryLeftSorted, 1, aryLeftSorted.length), aryRightSorted)) ;
        }else {
            result = concat(subArray(aryRightSorted, 0, 1) , merge(aryLeftSorted, subArray(aryRightSorted, 1, aryRightSorted.length))) ;
        }
        return result;
    }


    ///// Util Only below /////

    private static int[] concat(int[] first, int[] second){
        int[] both = Arrays.copyOf(first, first.length + second.length);
        System.arraycopy(second, 0, both, first.length, second.length);
        return both;
    }

    private static int[] copyArray(int[] array){
        return subArray(array, 0, array.length);
    }

    public static int[] subArray(int[] array, int beg, int end) {
        return Arrays.copyOfRange(array, beg, end);
    }

    private static void printArray(int[] ary){
        for (int i = 0; i < ary.length; i++) {
            System.out.printf("%4d" , ary[i]);
        }
        System.out.println();
    }
    private static void print2DArray(int[][] ary){
        for (int i = 0; i < ary.length; i++) {
            for (int j = 0; j < ary[i].length; j++) {
                System.out.printf("%4d" , ary[i][j]);
            }
            System.out.println();
        }
    }
}