import java.util.ArrayList;
public class Array{

    public static void mergesort(ArrayList list){
        if(list.size()-1>0){
            int middle=list.size()/2;
            ArrayList <Integer>leftList=new ArrayList();
            ArrayList <Integer>rightList=new ArrayList();

            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(ArrayList list,ArrayList leftList,ArrayList rightList){
        int middle=list.size()/2;
        int left=0,right=0;
        for(int i=0;i<middle;i++){//left side array
            leftList.add(i,list.get(i));
        }
        for(int i=middle;i<list.size();i++){//right side array
            rightList.add(i-middle,list.get(i));
        }
    }

    public static  void merge(ArrayList list,ArrayList <Integer>leftList,ArrayList <Integer>rightList){
        int left=0;int right=0;
        for(int i=0;left<leftList.size()&&right<rightList.size();i++){//copy left n right into list - increasing order
            int l=leftList.get(left);
            int r=rightList.get(right);
            list.remove(i);
            if(l>r){
                list.add(i,rightList.get(right));
                right++;
            }
            else{
                list.add(i,leftList.get(left));
                left++;
            }

        }
        for(int i=left;i<leftList.size();i++){//copy the rest of left into list
            list.remove(i+right);
            list.add(i+right,leftList.get(i));

        }
        for(int i=right;i<rightList.size();i++){//copy the rest of right into list
            list.remove(i+left);
            list.add(i+left,rightList.get(i));

        }

    }
    static public String display(ArrayList list){
        String str="["+list.get(0);
        for(int i=1;i<list.size();i++){
            str+=","+list.get(i);
        }
        str+="]";
        return str;
    }
}