Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 15

(a)

The merge method uses chain iterators to move through the input lists a and b. At any time in the first while loop below, elementA is the first unused element of list a, and elementB is the first unused element of list b. The smaller of these is appended to the output list. If the appended element came from a, we move to the next element of list a. Otherwise, we move to the next element of b.

---

public class MergeExtendedChain
{
   /** merge the sorted chains a and b */
   public static ExtendedChain merge(ExtendedChain a, ExtendedChain b)
   {
      // initialize iterators for a and b
      Iterator ia = a.iterator();     // iterator for a
      Iterator ib = b.iterator();     // iterator for b
      Comparable elementA = null;     // current element of a
      if (ia.hasNext())
         elementA = (Comparable) ia.next();
      Object elementB = null;         // current element of b
      if (ib.hasNext())
         elementB = ib.next();
   
      // create result chain
      ExtendedChain c = new ExtendedChain();
   
      // do the merge
      while (elementA != null && elementB != null)
      {
         if (elementA.compareTo(elementB) <= 0)
         {// elementA goes next
            c.add(elementA);
            if (ia.hasNext())
               elementA = (Comparable) ia.next();
            else
               elementA = null;
         }
         else
         {// elementB goes next
            c.add(elementB);
            if (ib.hasNext())
               elementB = ib.next();
            else
               elementB = null;
         }
      }
   
      // add remaining elements
      if (elementA != null)
         c.add(elementA);
      if (elementB != null)
         c.add(elementB);

      // at most one of a and b can be nonempty now
      while (ia.hasNext())
         c.add(ia.next());
   
      while (ib.hasNext())
         c.add(ib.next());
   
      return c;
   }
}

---

(b)

In each iteration of the first while loop, we move one node right in either a or b. So, the complexity of this loop is O(a.size + b.size). The complexity of the second while loop is O(a.size), and that of the third loop is O(b.size). So, the overall complexity is O(a.size + b.size).

(c)

The codes and output are in the files MergeExtendedChain.*.