/**
   * Merge two sorted sequences, S1 and S2, into a sorted sequence S.
   **/
  public static void merge(Sequence S1, Sequence S2, Comparator c, Sequence S) {
    while(!S1.isEmpty() && !S2.isEmpty())
      if(c.isLessThanOrEqualTo(S1.first().element(), S2.first().element()))
        S.insertLast(S1.remove(S1.first()));
      else
        S.insertLast(S2.remove(S2.first()));
    while(!S1.isEmpty()) // move the remaining elements of S1
      S.insertLast(S1.remove(S1.first()));
    while(!S2.isEmpty()) // move the remaining elements of S2
      S.insertLast(S2.remove(S2.first()));
  }