Combine two streams (ordered) to get the final sorted stream

Question

For example, how to combine two streams of sorted integers? I thought it was very thorough, but just found it non-trivial at all. Below, one is not tail recursive, and it will overflow the stack when the threads are large.

def merge(as: Stream[Int], bs: Stream[Int]): Stream[Int] = { (as, bs) match { case (Stream.Empty, bss) => bss case (ass, Stream.Empty) => ass case (a #:: ass, b #:: bss) => if (a < b) a #:: merge(ass, bs) else b #:: merge(as, bss) } } 

We might want to turn it into a tail recursive by introducing a battery. However, if we first close the battery, we will only get a stream of reverse order; if we add a concatenated battery (# :), it will no longer be lazy (strict).

What could be the solution? Thanks

Answer 1

By turning the comment back, there is nothing wrong with your merge.

It is not recursive at all - any call to merge returns a new thread without any other call to merge. a #:: merge(ass, bs) returns the stream with the first element a and where merge(ass, bs) will be called to evaluate the rest of the stream, when required.

So,

 val m = merge(Stream.from(1,2), Stream.from(2, 2)) //> m : Stream[Int] = Stream(1, ?) m.drop(10000000).take(1) //> res0: scala.collection.immutable.Stream[Int] = Stream(10000001, ?) 

works just fine. No.