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;
}
}