Merging two sequences in scala in an orderly fashion

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).

To interleave two sequences while maintaining their individual ordering, you can use:

scala> seq1.zip(seq2).flatMap(pair => Seq(pair._1,pair._2))
res1: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

Note, however, that for sequences of unequal length this loses the extra elements of the longer sequence. That can be sorted out with a bit more effort (find the longer of the two lists, and add longer.drop(shorter.length)).

I was happy to find @CaringDev's solution and to adapt it to use a Builder:

def mergeSortedBuilder[E: Ordering](x: Seq[E], y: Seq[E])(implicit ordering: Ordering[E]): Seq[E] = {
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Builder[E, Seq[E]]): Builder[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.newBuilder).result
}

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)