归并排序代码

package cn.shy.test;

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