import java.util.*; 
public class MergeSort { 
	/*;
	 !open *Background*
	 The |merge sort| algorithm is a well-known, highly used algorithm
	 for sorting in computer science, mostly due to its ease to understand
	 and its  $O(n$ $log$ $n)$ running time. The algorithm consists of
	 two parts, which I have split into two classes - Merge and MergeSort -
	 to reinforce the fact that they are two seperate areas. First, we'll 
	 look at MergeSort.
	 ;*/
	public ArrayList<Integer> mergeSort(ArrayList<Integer> l) { 
	/*;
	 !shut
	 The constructor takes an ArrayList as |input|. This is (in this 
	 implementation) the list of integers that we want to sort into the
	 correct order.
	 ;*/
		
		/*;
		 !open *Variable initialisation*
		 Some variables are declared before we start. |split1| and |split2|
		 refer to the two sub-arrays that will contain our sorted permutations.
		 Don't worry - this will be explained as we go along! Finally, |sorted|
		 is the array in which the result will be stored, and this will be returned.
		 ;*/
		ArrayList<Integer> split1 = new ArrayList<Integer>(); 
		ArrayList<Integer> split2 = new ArrayList<Integer>(); 
		ArrayList<Integer> sorted1 = new ArrayList<Integer>(); 
		ArrayList<Integer> sorted2 = new ArrayList<Integer>(); 
		ArrayList<Integer> sorted = new ArrayList<Integer>();
		/*;
		 !shut
		 With these variables initialised, it is now possible to look at the main
		 algorithm.
		 ;*/
		
		/*;
		 !open *An important check*
		 Below is an important piece of code:
		 ;*/
		if(l.size() <= 1) { 
			return l; 
		}
		/*;
		 !shut
		 If the array that has been input is either empty or of size 1, then we can just return it 
		 -- it is already sorted! This isn't just common sense; it prevents errors from occurring 
		 should this have been left unchecked. 
		 ;*/
		
		else { 
			int tmp = l.size()/2;
			/*;
			 !open *Splitting the input*
			 The first part of the algorithm involves splitting the input into two parts. There is no 
			 sorting going on here -- just simply halving it down the middle, as can be seen by checking 
			 to see if $i<l\div 2$.
			 ;*/
			for(int i = 0; i < l.size(); i++) { 
				int x=l.get(i); 
				if(i < tmp) { 
					split1.add(x); 
				} 
				else { 
					split2.add(x); 
				} 
			} 
			
			/*;
			 !shut
			 At the end of this for loop, the whole of |l| will have been iterated over, with the first
			 half residing in |split1| and the second in |split2|.
			 ;*/
			
			/*;
			 !open *The magic of recursion*
			 This is the part that makes merge sort so powerful: |recursion|. Here, the algorithm calls
			 itself on the two halves of the input. These will be halved again, and again, and again...
			 until the check at the top of the algorithm fails. This was that the input must be greater 
			 than 1 in size, remember? 
			 ;*/
			sorted1 = mergeSort(split1); 
			sorted2 = mergeSort(split2); 
			sorted = new Merge().merge(sorted1,sorted2); 
			return sorted; 
			/*;
			 !shut
			 At the time we get to the |return| statement in the top-most merge sort method, recursive 
			 calls have occurred so that the original input has been broken down into singular lists 
			 just one element. Pairs at each level in the |computation tree|, starting at the bottom, 
			 are then merged by the merge algorithm into the correct order. This occurs all the way up 
			 the tree until we arrive at the top, with all elements in one list in the correct order. 
			 ;*/
		} 
	} 
}