title: Merge Two Streams
body: <p>I am trying to implement a method to merge the values in two <code>Stream</code>s based on a <code>Comparator</code> for the values.</p>
  
  <p>I had a way to do this, where I iterate over the streams and insert the values into a <code>Stream.Builder</code>, but I have not been able to figure out how to make a lazy-evaluated version (the way many stream operations are), so it can deal with infinite streams as well.</p>
  
  <p>All I want it to do is perform a <em>single</em> merging pass on the input data, <em>not</em> sort the streams (in fact, it is likely that the streams will be disordered; this disorder needs to be preserved).</p>
  
  <pre><code>static Stream&lt;E&gt; merge(Stream&lt;E&gt; first, Stream&lt;E&gt; second, Comparator&lt;E&gt; c)
  </code></pre>
  
  <p>How can I lazily merge two streams like this?</p>
  
  <p>If I were doing this with two <code>Queue</code>s as input and some <code>Consumer</code> as output, it would be fairly simple:</p>
  
  <pre><code>void merge(Queue&lt;E&gt; first, Queue&lt;E&gt; second, Consumer&lt;E&gt; out, Comparator&lt;E&gt; c){
      while(!first.isEmpty() &amp;&amp; !second.isEmpty()
          if(c.compare(first.peek(), second.peek()) &lt;= 0)
              out.accept(first.remove());
          else
              out.accept(second.remove());
      for(E e:first)
          out.accept(e);
      for(E e:second)
          out.accept(e);
  }
  </code></pre>
  
  <p>But I need to do this with lazy evaluation, and streams.</p>
  
  <p>To address the comments, here are some example inputs and the result:</p>
  
  <p>Example 1:</p>
  
  <pre><code>merge(
      Stream.of(1, 2, 3, 1, 2, 3),
      Stream.of(2, 2, 3, 2, 2, 2),
      Comparator.naturalOrder()
  );
  </code></pre>
  
  <p>would return a stream that would produce this sequence:</p>
  
  <pre><code>1, 2, 2, 2, 3, 3, 1, 2, 2, 2, 2, 3
  </code></pre>
  
  <p>Example 2:</p>
  
  <pre><code>merge(
      Stream.iterate(5, i-&gt;i-1),
      Stream.iterate(1, i-&gt;i+1),
      Comparator.naturalOrder()
  );
  </code></pre>
  
  <p>would return an infinite (well, an <code>INT_MAX + 5</code> item) stream that would produce the sequence:</p>
  
  <pre><code>1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0, -1 ...
  </code></pre>
  
  <p>As you can see, this is not merely <code>concat(first,second).sort()</code>, since (a) you can't sort infinite streams, and (b) even when you can sort the streams, it does not give the desired result.</p>