import java.util.*; 
public class Merge { 
/*;
 !open *Introduction*
 The |merge| algorithm is a crucial part of the merge sort algorithm; it
 couldn't function without it. The idea behind merge is that it takes two
 data structures -- in this case |ArrayList| -- which are called |l| and |m|.
 ;*/
public ArrayList<Integer> merge (ArrayList<Integer> l, ArrayList<Integer> m) { 
/*;
 !shut
 Above is the header of the actual merge method, showing the two inputs and
 its return type: another ArrayList.
 ;*/
	
	/*;
	 !open *Variable initialisation*
	 We need to initialise three additional variables in this particular implementation.
	 Firstly, another ArrayList is required called |result|, in which sorted elements will
	 be added as the algorithm runs. The two integers, |i| and |j|, will be used to keep
	 track of the current position in the list |l| and |m| respectively.
	 ;*/
	ArrayList<Integer> result = new ArrayList<Integer>(); 
	int i = 0; 
	int j = 0; 
	
	/*;
	 !shut
	 Now that these have been declared, we can move on to looking at the main merge
	 algorithm.
	 ;*/
	
	/*;
	 !open *The merge algorithm*
	 The purpose of this while loop is to do the following. Firstly, we must only
	 enter while our result array is smaller than the sum of the sizes of the two
	 input arrays. This makes sense, and ensures that we avoid a |null pointer|
	 error. The outer if construct checks that the two indexes have not incremented
	 past the size of our two input arrays. Again, this prevents |null pointer| 
	 exceptions. If the pointers are less, then we compare the |i|th and |j|th elements
	 in both arrays. The smallest gets added to the result array, and the index of that
	 array is incremented.
	 ;*/
	while(result.size() < (l.size() + m.size())) { 
			if(l.size() > i && m.size() > j) { 
				if(l.get(i) < m.get(j)) { 
					result.add(l.get(i++)); 
				} 
				else { 
					result.add(m.get(j++)); 
				} 
			} 
			else if (l.size() > i) { 
				result.add(l.get(i++)); 
			} 
			else if (m.size() > j) { 
				result.add(m.get(j++)); 
			} 
	} 
	/*;
	 !shut
	 When the outer if guard fails, either $i\leq result.size()$ or $j\leq result.size()$.
	 Therefore, this means that the other input array will have some elements left that
	 need to be copied into |result|. The while loop continues executing, and each remaining
	 iteration will add another `left over' element to the result array, until the while's
	 outer guard fails.
	 ;*/
	
	/*;
	 !open *Returning and speed*
	 At this point in the code, the algorithm has finished. All that remains to do is |return|
	 the result.
	 ;*/
	return result;
	/*;
	 !shut
	 The overall efficiency of the merge algorithm is $O(n)$. This is because every time that
	 merge will be called, it will be working on some divided portion of the tree -- let us call
	 the size of that portion $m$. At each level in the tree, all portions of $O(m)$ will always
	 add up to $O(n)$. Therefore, $O(m)+O(m)+...+O(m)=O(n)$.
	 ;*/
	} 
}