edtechre

		// Partition list in half
		int m = size / 2;
		List<Integer> left = new ArrayList<Integer>();
		List<Integer> right = new ArrayList<Integer>();
		for (int i = 0; i < m; i++) {
			left.add(list.get(i));
		}
		for (int i = m; i < size; i++) {
			right.add(list.get(i));
		}
		
		// Recursively merge sort each partition
		left = mergeSort(left);
		right = mergeSort(right);
		
		// If the last element of the left partition is greater than the first element of the right partition
		// The left and right partitions need to be rearranged
		if (left.get(left.size() - 1) > right.get(0)) {
			return merge(left, right);
		// Otherwise left and right partitions are in the correct order
		} else {
			left.addAll(right);
			return left;
		}
	}
	
	protected List<Integer> merge(List<Integer> left, List<Integer> right) {
		List<Integer> result = new ArrayList<Integer>();
		// While both containers are non-empty
		// Move lesser elements to the front of the result, and remove them from their containers
		while (!left.isEmpty() && !right.isEmpty()) {
			if (left.get(0) < right.get(0)) {
				result.add(left.remove(0));
			} else {
				result.add(right.remove(0));
			}
		}
		// The container that still has elements contains elements greater than those in the other container
		// It is assumed that the elements in the container are also already sorted
		// So the non-empty container's elements should be appended to the end of the list
		if (!left.isEmpty()) {
			result.addAll(left);
		} else {
			result.addAll(right);
		}
		return result;
	}