Finds the elements shared by 2 lists, FP style, recursively

Intersect.scala

object Intersect extends App{

  import scala.annotation.tailrec

  // finds the elements shared by 2 lists, FP style, recursively
  // O(n log n)

  @tailrec
  def scan(x: List[Int], y: List[Int], out: List[Int] = List.empty[Int]): List[Int] =
    (x, y) match {
      case (xhead :: xtail, yhead :: ytail) =>
        if (xhead == yhead) scan(xtail, ytail, xhead :: out)
        else if (xhead < yhead) scan(xtail, y, out)
        else scan(x, ytail, out)
      case _ => out
    }

  def intersect(x: List[Int], y: List[Int]): List[Int] =
    scan(x.sorted, y.sorted).reverse

  val li1 = List(3, 6, 7, 1, 2)
  val li2 = List(4, 5, 1, 6, 3, 20, 0)

  println(intersect(li1, li2))
  // sanity check, here we use Scala's inbuilt Set functionality
  println(li1.toSet.intersect(li2.toSet))
  // sanity check, and in built intersect
  println(li1.intersect(li2))

  // all the above show that common elements are 1, 3 and 6

}