Merge Sort in Scala

Merge Sort is a kind of fast sorting algorithm with O(nlog(n)) order.

Merge sort itself is a recursive algorithm and can be expressed neatly even in an Imperative programming like Java. However pattern matching and high order functions in Scala can make this even interesting.

def mergeSort(list:List[Int]):List[Int] = list match {
 case x::Nil=> List(x)
 case _ =>
   val (a, b) = list.splitAt(list.length /2)
   merge(mergeSort(a), mergeSort(b))     
}

def merge(aList:List[Int], bList:List[Int]):List[Int]= bList match {       
 case Nil => aList
 case _ =>
   aList match {
   case Nil => bList
   case x::xs =>
     if (x < bList.head)
    x::merge(xs, bList)
     else
    bList.head::merge(aList, bList.tail)               
   }   
}