import java.util.*;

public class MergeSortDemo
{
	<L extends List> L<T> Merge(L<T> left, L<T> right)
	{
		L<T> d = new L<T>();
	
		while (left.length() > 0 && right.length() > 0)
			if(left.get(0) <= right.get(0))
				d.add(left.remove(0));
			else
				d.add(right.remove(0));
	
		if (left.length() > 0) d.addAll(left);
		if (right.length() > 0) d.addAll(right);
	
		return d;
	}

	<L extends List> L<T> MergeSort(L<T> d)
	{
		if (d.length() == 1) return d;
	
		L left = new L();
		L right = new L();
	
		int middle = d.length() / 2;
	
		left = d.subList(0, middle);
		right = d.subList(middle, d.length());
	
		left = MergeSort(left);
		right = MergeSort(right);
		return Merge(left, right);
	}

	public static void main(String[] args)
	{
		ArrayList<Integer> IntegerList = new ArrayList<Integer>();

		IntegerList.add(new Integer(4));
		IntegerList.add(new Integer(8));
		IntegerList.add(new Integer(2));
		IntegerList.add(new Integer(7));
		IntegerList.add(new Integer(3));
		IntegerList.add(new Integer(7));
		IntegerList.add(new Integer(12));
		IntegerList.add(new Integer(10));
		IntegerList.add(new Integer(9));
		IntegerList.add(new Integer(6));
		IntegerList.add(new Integer(5));
		IntegerList.add(new Integer(1));

		System.out.println("IntegerList before sorting:");
		System.out.println(IntegerList);

		IntegerList = MergeSort(IntegerList);

		System.out.println("IntegerList before sorting:");
		System.out.println(IntegerList);
	}
}