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

public class Merge {
 public static <E extends Comparable<? super E>> List<E> mergeSort(List<E> m) {
  if(m.size() <= 1) return m;

  int middle = m.size() / 2;
  List<E> left = m.subList(0, middle);
  List<E> right = m.subList(middle, m.size());

  right = mergeSort(right);
  left = mergeSort(left);
  List<E> result = merge(left, right);

  return result;
 }

 public static <E extends Comparable<? super E>> List<E> merge(List<E> left, List<E> right) {
  List<E> result = new ArrayList<E>();
  Iterator<E> it1 = left.iterator();
  Iterator<E> it2 = right.iterator();

  E x = it1.next();
  E y = it2.next();
  while (true) {
    //change the direction of this comparison to change the direction of the sort
    if(x.compareTo(y) <= 0) {
       result.add(x);
       if(it1.hasNext()) {
            x = it1.next();
       } else {
            result.add(y);
            while(it2.hasNext()) {
                    result.add(it2.next());
            }
            break;
       }
 } else {
       result.add(y);
       if(it2.hasNext()) {
       y = it2.next();
       } else {
            result.add(x);
            while (it1.hasNext()) {
                    result.add(it1.next());
            }
            break;
       }
    }
  }
  return result;
 }
}