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


public class SortDemo {
	
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
	    list.add(3);
	    list.add(7);
	    list.add(1);
	    list.add(23);
	    list.add(5);
	    list.add(2);
	    
	    System.out.println("list        : " + list);
	    
	    List<Integer> sortedList = mergesort(list);
	    System.out.println("sorted list : " + sortedList);
	}

	private static List<Integer> mergesort(List<Integer> list) { 
		if (list.size() <= 1) return list;
		int size = list.size();
		List<Integer> first = mergesort(list.subList(0,size/2 ));
		List<Integer> second = mergesort(list.subList(size/2,size));
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		int pos1 = 0;
		int pos2 = 0;
		
		while ((pos1 < first.size() || pos2 < second.size()) ) {
			if (pos1 == first.size() || (pos2 < second.size() && first.get(pos1) > second.get(pos2))) {
				result.add(second.get(pos2));
				pos2++;
			} else {
				result.add(first.get(pos1));
				pos1++;
			}
		}
		return result;
	}
	
    
    
    
	
	
	
	
}