import java.util.ArrayList;
public class Merge
{
	public static ArrayList<Comparable> merge(ArrayList<Comparable> list1,
	                                   ArrayList<Comparable> list2)
	{
		ArrayList<Comparable> listOne = copy(list1);
		ArrayList<Comparable> listTwo = copy(list2);
	
		if (listOne.isEmpty())
			return listTwo;
			
		if (listTwo.isEmpty())
			return listOne;
	
		Comparable small;
		if (listOne.get(0).compareTo(listTwo.get(0)) < 0)
			small = listOne.remove(0);
		else
			small = listTwo.remove(0);
		
		ArrayList<Comparable> both = merge(listOne, listTwo);
		both.add(0, small);
		return both;
	}
	
	public static void sort(ArrayList<Comparable> list)
	{
		if (list.size() > 1)
		{
			ArrayList<Comparable> left = new ArrayList<Comparable>();
			ArrayList<Comparable> rite = new ArrayList<Comparable>();
			split(list, left, rite);
			sort(left);
			sort(rite);
			ArrayList<Comparable> items = merge(left, rite);
			list.clear();
			for (Comparable item : items)
				list.add(item);
		}
	}
	
	private static void split(ArrayList<Comparable> list, ArrayList<Comparable> left,
	                                                      ArrayList<Comparable> rite)
	{
		int middle = list.size() / 2;
		
		int k;
		for(k = 0; k < middle; k++)
			left.add(list.get(k));
			
		for ( ; k < list.size(); k++)
			rite.add(list.get(k));
	}
	
	private static ArrayList<Comparable> copy(ArrayList<Comparable> original)
	{
		ArrayList<Comparable> duplicate = new ArrayList<Comparable>();
		
		for (Comparable item : original)
			duplicate.add(item);
			
		return duplicate;
	}
}