Why this rather than java.util.PriorityQueue? The two approaches have he
same computational complexity, but the PriorityQueue implementation
should be much simpler.

Patricia

I kind of thought that might help, but couldn't think of a way to
implement it efficiently. In a burst of caffeine, though, I produced the
following code. Thanks for the inspiration. This is elegant. The only
thing I don't like about it is all the casting required, but that's the
cost of using Collections.

/**
 * Wraps multiple Iterators, and returns the Objects in the Iterators
 * in the correct, ascending sequence. Assumes that the Iterators
 * contain Objects that implement the Comparable interface.
 */
public class MergingIterator implements Iterator {
  private PriorityQueue queue = new PriorityQueue();

  public void add(Iterator it) {
    if (!it.hasNext())
      return; // do nothing, do not add

    Carrier carrier = new Carrier();
    carrier.it = it;
    carrier.next = (Comparable)it.next();
    queue.offer(carrier);
  }

  public boolean hasNext() {
    return !queue.isEmpty();
  }

  public Object next() {
     Carrier carrier = (Carrier)queue.poll();
     Comparable next = carrier.next;

     // if there's another object to be had from this stream, insert it.
     // if not, the queue just gets smaller
     if (carrier.it.hasNext()) {
       carrier.next = (Comparable) carrier.it.next();
       queue.offer(carrier);
     }

    return next;
  }

  public void remove() {
    throw new UnsupportedOperationException();
  }

  private class Carrier implements Comparable {
    Iterator it;
    Comparable next;

    public int compareTo(Object other) {
      return next.compareTo(((Carrier)other).next);
    }
  }
}