/**
   * Sort the elements of list L in nondecreasing order according
   * to comparator c, using the merge-sort algorithm.
   **/
  public static void mergeSort (List L, Comparator c) {
    int n = L.size();
    if (n < 2) 
      return;  // the list L is already sorted in this case
    // divide
    List L1 = new NodeList(); // first list used in recursion
    List L2 = new NodeList(); // second list used in recursion
    int i = 0;
    while (i < n/2) {
      L1.insertLast(L.remove(L.first())); // move the first n/2 elements to L1
      i++;
    }
    while (!L.isEmpty())
      L2.insertLast(L.remove(L.first())); // move the rest to L2
    // recurse
    mergeSort(L1,c);
    mergeSort(L2,c);
    //conquer
    merge(L1,L2,c,L);
  }