CareerCup

public static void merge(List<Stream> inputStreams, Stream outputStream) {
  PriorityQueue<PQKeyVal> q = new PriorityQueue<PQKeyVal>();
  for (Stream s: inputStreams) {
    q.add(new PQKeyVal(s));
  }
  for (;;)
  {
    PQKeyVal top = q.poll();
    outputStream.put(top.key);
    top.stream.poll();
    q.offer(new PQKeyVal(top.stream));
  }
}

where PQKeyVal defined like that:

class PQKeyVal implements Comparable<PQKeyVal> {
  public final int key;
  public final Stream stream;
  public PQKeyVal(Stream stream) {
    this.stream = stream;
    this.key = stream.peek();
  }

  @Override
  public int compareTo(PQKeyVal that) {
    return this.key - that.key;
  }
}

We can use a priority queue where the key is the head value and the value is a pointer to the corresponding stream. We just need to repeatedly pop the min element, output the key, advance the stream to the next element and push it back to the queue using the new head value.