Recursive Merge Sort.

gistfile1.scala

// merge calls itself recursively
def merge(l1: List[Int], l2: List[Int]): List[Int] = {
  // termination cases
  if (l1.length == 0 && l2.length == 0) return Nil
  if (l1.length == 0) return l2.head :: merge(Nil, l2.tail)
  if (l2.length == 0) return l1.head :: merge(Nil, l1.tail)
  l1.head.compare(l2.head) match {
    case -1 => l1.head :: merge(l1.tail, l2)
    case _  => l2.head :: merge(l2.tail, l1)
  }
}

// mergeSort calls itself AND merge recursively
def mergeSort(list: List[Int]): List[Int] = {
  // termination case
  if (list.length < 2)
    list
  else {
    val part = list.splitAt(list.length / 2)
    merge(mergeSort(part._1), mergeSort(part._2))
  }
}