import java.util.*;
public class MergesortTest {
//
public List<Integer> merge(List<Integer> left,List<Integer> right){
List<Integer> result = new ArrayList<Integer>();
while(left.size()>0 && right.size()>0){
if((Integer)left.get(0).intValue()<=(Integer)right.get(0).intValue()){
result.add(left.get(0));
left.remove(0);
}else {
result.add(right.get(0));
right.remove(0);
}
}
if (left.size()>0){
for(Iterator<Integer> iter = left.iterator();iter.hasNext();) {
result.add(iter.next());
}
}
if(right.size()>0) {
for(Iterator<Integer> iter =right.iterator();iter.hasNext();){
result.add(iter.next());
}
}
return result;
}
public List<Integer> mergesort(List<Integer> data) {
if(data.size()<=1) {
return data;
}
int middle = data.size()/2;
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
for (int i=0;i<middle;i++) {
left.add(data.get(i));
}
for (int i=middle;i<data.size();i++) {
right.add(data.get(i));
}
left =mergesort(left);
right=mergesort(right);
List<Integer> res =merge(left,right);
return res;
}
public static void main(String[] args) {
MergesortTest mt=new MergesortTest();
List<Integer> list1 = new ArrayList<Integer>();
list1.add(1);
list1.add(3);
list1.add(6);
list1.add(2);
list1.add(4);
list1.add(7);
list1.add(0);
list1.add(9);
List<Integer> res=mt.mergesort(list1);
for (Integer i : res) {
System.out.println(i);
}
}
}