Merge two sequences in scala in an ordered manner

Question

I am trying to combine two sequences so that they will be sorted. Below is the code I wrote:

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 required result should be:

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

But it doesn't seem to break in Scala. I am relatively new to the language. What would be the best way to perform this operation?

Answer 1

The easiest way is probably the following:

 (seq1 ++ seq2).sorted 

If seq1 and seq1 contain a different type, you need to specify Ordering for this type; or, alternatively, use the sortBy method, matching each element with an element of a different type for which Ordering can be implicitly found:

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

Answer 2

The following also works for non-migrated 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()) } 

Note that for performance reasons, you are probably using Builders (vs .: +, + :, reverse).

Answer 3

I was happy to find @CaringDev's solution and adapt it to use 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 } 

Answer 4

To alternate two sequences while saving their individual order, 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 additional elements of a longer sequence. This can be sorted with less effort (find the longer of the two lists and add longer.drop(shorter.length) ).

Answer 5

If you want to alternate an arbitrary number of sequences in order, you can use something like

 implicit class Interleave[T](input: Seq[Seq[T]]) { def interleave: Seq[T] = { input.foldLeft(Seq[Seq[T]]()) { (acc, cur) => if (acc.isEmpty) cur.map { m => Seq(m) } else (acc zip cur).map { case (sequence, m) => sequence :+ m } }.flatten.toVector } } 

It may be possible to improve performance on this, especially since toVector exists primarily to convert the stream to something impatient.

Usage looks something like this

 Seq(Seq(1,2), Seq(2,3), Seq(3,4)).interleave should be(Seq(1,2,3,2,3,4))