import java.util.ArrayList;
import java.util.List;

public class MergeSort {

	public MergeSort() {
	}

	public List<Integer> mergeSort(List<Integer> list) {
		if(list!=null){
			List<Integer> left = new ArrayList<Integer>();
			List<Integer> right = new ArrayList<Integer>();
			List<Integer> result = new ArrayList<Integer>();
			if(list.size()<=1)
				return list;
			int middle = list.size()/2;
			for(int i=0;i<list.size();i++){
				if(i<middle)
					left.add(list.get(i));
				else
					right.add(list.get(i));
			}
			left = mergeSort(left);
			right = mergeSort(right);
			result = mergeSort(left, right);
			return result;
		}
		return list;
	}

	private List<Integer> mergeSort(List<Integer> left, List<Integer> right) {
		List<Integer> result = new ArrayList<Integer>();
		int counterLeft = 0;
		int counterRight = 0;
		while(counterLeft<left.size() && counterRight<right.size()){
			Integer leftId = left.get(counterLeft);
			Integer rightId = right.get(counterRight);
			if(leftId.intValue()<=rightId.intValue()){
				result.add(leftId);
				counterLeft++;
			}else{
				result.add(rightId);
				counterRight++;
			}
		}
		while(counterLeft<left.size()){
			result.add(left.get(counterLeft));
			counterLeft++;
		}
		while(counterRight<right.size()){
			result.add(right.get(counterRight));
			counterRight++;
		}
		return result;
	}
}