import java.util.Arrays;


public class MergeSort {

    /**
     * @param args
     */
    int binarySearch(int v, int[] list, int left, int right){
        if(left > right) return -1;
        int m = (left+right)/2;
        if(list[m] == v) return m;
        if(list[m] > v) return binarySearch(v, list, 0, m-1);
        /*if(list[m] < v)*/ return binarySearch(v, list, m+1, right);
    }
    public static int[] mergeSort(int[] list){
        if(list.length <= 1) return list;
        int m=list.length/2;
        int[] left = Arrays.copyOfRange(list, 0,m);
        int[] right = Arrays.copyOfRange(list, m, list.length);
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }
    public static int[] merge(int[] left, int[] right){
        int l = left.length + right.length;
        int[] result = new int[l];
        int curr=0;
        while(left.length > 0 && right.length > 0){
            if(left[0] < right[0]){
                result[curr] = left[0];
                left = Arrays.copyOfRange(left, 1,left.length);
            }
            else{
                result[curr] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
            curr++;
        }
        while(left.length > 0){
            result[curr] = left[0];
            left = Arrays.copyOfRange(left, 1,left.length);
            curr++;
        }
        while(right.length > 0){
            result[curr] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
            curr++;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{100, 29,33,1,243,21,1233,112,1,1,1,1,333,11,1234})));

    }

}