Merging two sequences in scala in an orderly fashion

Question

I am trying to merge two sequences such that they remain sorted. The following is the code that I have written:

  val seq1 = Seq(1,3,5,7,9)
  val seq2 = Seq(2,4,6,8)
  var arr = Seq[Int]()
  for(b <- seq2)
  {
    for(a <- seq1)
    {
      if(a < b)
        arr = arr :+ a
      else
      {
        arr = arr :+ b;break; 
      }
    }
  }
  println(arr)

the output that I require needs to be :

Seq(1,2,3,4,5,6,7,8,9)    

But it seems break does not work in Scala. I am relatively new to the language. What would be the best way to carry out this operation?

Answer 1

The simplest way would probably be this:

(seq1 ++ seq2).sorted

If seq1 and seq2 contain some other type, you'll have to provide an Ordering for that type; or, alternatively, use the sortBy method, mapping each element to an element of another type for which an Ordering can implicitly be found:

(seq1 ++ seq2).sortBy(_.toDate)

Answer 2

The following also works for non-interleaved sequences:

def mergeSorted[E: Ordering](x: Seq[E], y: Seq[E]): Seq[E] = {
  val ordering = implicitly[Ordering[E]]
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Seq[E]): Seq[E] = {
    (x, y) match {
      case (Nil, Nil) => acc
      case (_, Nil)   => acc ++ x
      case (Nil, _)   => acc ++ y
      case (xh :: xt, yh :: yt) =>
        if (ordering.lteq(xh, yh))
          rec(xt, y, acc :+ xh)
        else
          rec(x, yt, acc :+ yh)
    }
  }
  rec(x, y, Seq())
}

Please note that for performance reasons you'd probably use Builders (vs. :+, +:, reverse).