Scala: Merge sort for lists with pattern binding and pairs

merge_sort.scala

// Pairs are a subset of Scala tuples
val pair = ("answer", 42)
val label = pair._1
val (label, value) = pair // Pattern binding

// Merge sort
// * Separate the list into two sub-lists,
//   each containing around half of the elements of the original list
// * Sort the two sub-lists
// * Merge the two sorted sub-lists into a single sorted list
def msort(xs: List[Int]): List[Int] = {
  val n = xs.length / 2
  if (n == 0) xs
  else {
    def merge(xs: List[Int], ys: List[Int]) = ???
    val (fst, snd) = xs splitAt n
    merge(msort(fst), msort(snd))
  }
}

// The merge function could be written as follows
def merge(xs: List[Int], ys: List[Int]) = {
  xs match {
    case Nil =>
      ys
    case x :: xs1 =>
      ys match {
        case Nil =>
          xs
        case y :: ys1 =>
          if (x < y) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }
  }
}

// But its much easier to understand if we use pairs:
def merge(xs: List[Int], ys: List[Int]) = {
  (xs, ys) match {
    case (xs, Nil) => xs
    case (Nil, ys) => ys
    case (x :: xs1, y :: ys1) =>
      if (x < y) x :: merge(xs1, ys)
      else y :: merge(xs, ys1) 
  }
}