public class Array{

    public static void mergesort(int []list){
        if(list.length-1>0){
            int middle=list.length/2;
            int []leftList=new int[middle];
            int []rightList=new int[list.length-middle];

            divide(list,leftList,rightList);//divide list into two array - left 'n' right

            mergesort(leftList);//recursive for left side
            mergesort(rightList);//recursive for right side

            merge(list,leftList,rightList);//merge
        }
    }

    public static void divide(int []list,int []leftList,int []rightList){
        int middle=list.length/2;
        int left=0,right=0;
        for(int i=0;i<middle;i++){//left side array
            leftList[i]=list[i];
        }
        for(int i=middle;i<list.length;i++){//right side array
            rightList[i-middle]=list[i];
        }
    }

    public static  void merge(int []list,int []leftList,int []rightList){
        int left=0;int right=0;
        for(int i=0;left<leftList.length&&right<rightList.length;i++){//copy left n right into list - increasing order
            if(leftList[left]>rightList[right]){
                list[i]=rightList[right];
                right++;
            }
            else{
                list[i]=leftList[left];
                left++;
            }
        }
        for(int i=left;i<leftList.length;i++){//copy the rest of left into list
            list[i+right]=leftList[i];
        }
        for(int i=right;i<rightList.length;i++){//copy the rest of right into list
            list[i+left]=rightList[i];
        }

    }
}