Merge Two Streams

You need to implement a Spliterator, rather than going through Stream.Builder. For this, you might even just go through an Iterator, since it's a fairly sequential operation. Using Guava lightly,

return StreamSupport.stream(Spliterators.spliteratorUnknownSize(
    Iterators.mergeSorted(
      Arrays.asList(stream1.iterator(), stream2.iterator()),
      comparator),
    Spliterator.ORDERED),
  false /* not parallel */ );