import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {-1,2,6,5,4,7,8,9,11,0};
        System.out.println(Arrays.toString(sort(arr)));
        sortinplace(arr,0, arr.length);
        System.out.println(Arrays.toString(arr));

    }

    private static void sortinplace(int[] arr,int s , int e) {
        if(e-s==1)
            return;
        int mid = (e + s)/2;
        sortinplace(arr,s,mid);
        sortinplace(arr,mid,e);
        mergeplace(arr,s,mid,e);
    }
    private static void mergeplace(int[] arr , int s, int m , int e){
        int[] mix = new int[e-s];
        int i = s;
        int j = m;
        int k = 0;
        while(i<m && j<e){
            if(arr[i]>arr[j]) {
                mix[k] = arr[j];
                j++;
            }
            else {
                mix[k] = arr[i];
                i++;
            }
            k++;
        }
        while(i<m){
            mix[k]=arr[i];
            i++;
            k++;
        }
        while(j<e){
            mix[k]=arr[j];
            j++;
            k++;
        }

        for(i = 0 ; i < mix.length ; i++){
            arr[s+i]=mix[i];
        }

    }

    private static int[] sort(int[] arr) {
        if(arr.length==1)
            return arr;
        int mid = arr.length/2;
        int[] left = sort(Arrays.copyOfRange(arr,0,mid));
        int[] right = sort(Arrays.copyOfRange(arr,mid,arr.length));
        return merge(left, right);
    }

    private static int[] merge(int[] first, int[] second) {
        int[] mix = new int[first.length+second.length];
        int i=0,j=0,k=0;
        while(i<first.length && j<second.length){
            if(first[i]<second[j]) {
                mix[k] = first[i];
                i++;
            }
            else{
                mix[k]=second[j];
                j++;
            }
            k++;
        }
        while(i<first.length){
            mix[k]=first[i];
            i++;
            k++;
        }
        while(j<second.length){
            mix[k]=second[j];
            j++;
            k++;
        }
        return mix;
    }
}