msort.scala

def mergeSort(xs: List[Int]): List[Int] = {
  val n = xs.length / 2
  if (n == 0) xs
  else {
    val (firstHalf, secondHalf) = xs splitAt n
    merge(mergeSort(firstHalf), mergeSort(secondHalf))
  }
}

def merge(xs: List[Int], ys: List[Int]): List[Int] =
  (xs, ys) match {
    case (Nil, ys) => ys
    case (xs, Nil) => xs
    case (x :: xTail, y :: yTail) =>
      if (x < y) x :: merge(xTail, ys) else y :: merge(yTail, xs)
  }