List<Integer> merge(List<Integer> left, List<Integer> right) {

		int leftI = 0;
		int rightI = 0;

		List<Integer> merged = new ArrayList<Integer>(left.size() + right.size());

		while (leftI < left.size() && rightI < right.size()) {
			if (left.get(leftI) < right.get(rightI)) {
				merged.add(left.get(leftI));
				leftI++;
			} else {
				merged.add(right.get(rightI));
				rightI++;
			}
		}
		while (leftI < left.size()) {
			merged.add(left.get(leftI));
			leftI++;
		}
		while (rightI < right.size()) {
			merged.add(right.get(rightI));
			rightI++;
		}

		return merged;
	}