import java.util.Arrays;
public class MyMergeSort{
    public static void sort(int[] a){
        if (a.length <= 1)
            return;
        int mid=a.length/2;
        int[] left=Arrays.copyOfRange(a,0,mid);
        int[] right=Arrays.copyOfRange(a,mid,a.length);
        sort(left);
        sort(right);
        merge(left,right,a);
    }
    public static void
        merge(int[] a, int[] b, int[] out){
        int aIndex=0, bIndex=0;
        for (int i=0; i<out.length; i++){
            if(aIndex >= a.length)
                out[i]=b[bIndex++];
            else if (bIndex >= b.length)
                out[i]=a[aIndex++];
            else if (a[aIndex] <= b[bIndex])
                out[i]=a[aIndex++];
            else
                out[i]=b[bIndex++];
        }
    }
    public static void main(String[] args){
        int [] data= ArrayUtil.randomIntArray(10,1000);

        ArrayUtil.print(data);

        sort(data);

        ArrayUtil.print(data);

    }

}
//