MergeSort.scala

def split[T <% Ordered[T]](list: List[T]): (List[T], List[T]) =
  list match {
    case Nil => (Nil, Nil)
    case head :: Nil => (head :: Nil, Nil)
    case first :: second :: tail =>
      val (tl1, tl2) = split(tail)
      (first :: tl1, second :: tl2)
  }

def merge[T <% Ordered[T]](list1: List[T], list2: List[T]): List[T] =
  (list1, list2) match {
    case (x, Nil) => x
    case (Nil, y) => y
    case (flh :: flt, slh :: slt) =>
    	if (flh > slh)
      	slh :: merge(list1, slt)
      else
      	flh :: merge(flt, list2)
  }

def mergeSort[T <% Ordered[T]](list: List[T]): List[T] =
  list match {
    case Nil | _ :: Nil =>
      list
    case _ =>
      val (part1, part2) = split(list) //list.splitAt(list.length / 2)
      val sorted1 = mergeSort(part1)
      val sorted2 = mergeSort(part2)
      merge(sorted1, sorted2)
  }