public class MyMergeSort{
    public static void sort(int[] a){

        if (a.length <= 1)
            return;
        int mid=a.length/2;
        int[] left=new int[mid];
        int[] right=new int[a.length-mid];
        for (int i=0; i<mid; i++)
            left[i]=a[i];
        for (int i=0; i<right.length; i++)
            right[i]=a[mid+i];
        sort(left);
        sort(right);
        merge(left,right,a);
    }
    public static void merge(int []a, int[] b,
                             int[] dest){
        int aIndex=0;
        int bIndex=0;
        for (int destIndex=0;
             destIndex<dest.length; destIndex++){
            if(aIndex >= a.length){
                dest[destIndex]=b[bIndex++];
            } else if (bIndex >= b.length){
                dest[destIndex]=a[aIndex++];
            } else if (a[aIndex] <= b[bIndex]) {
                dest[destIndex]=a[aIndex++];
            } else {
                dest[destIndex]=b[bIndex++];
            }
        }
    }
    public static void main(String[] args){
        int [] data= ArrayUtil.randomIntArray(10,1000);

        ArrayUtil.print(data);

        sort(data);

        ArrayUtil.print(data);

    }

}
//