Generic merge sort based on elements having an Ordered typeclass implementation

merge-sort.scala

def mergeSort[T](list: List[T])(implicit ordering: Ordering[T]): List[T] = {
  def merge(l: List[T], r: List[T]): List[T] =
    (l, r) match {
      case (lHead:: lTail, rHead :: rTail) if ordering.lteq(lHead, rHead) => lHead :: merge(lTail, r)

      case (lHead:: lTail, rHead :: rTail) => rHead :: merge(l, rTail)

      case (x, Nil) => x

      case (Nil, y) => y

      case (Nil, Nil) => Nil
    }

  val halfway = list.length / 2
  if (halfway == 0) list  // list is empty or list is single value
  else {
    val (left, right) = list.splitAt(halfway)
    merge(mergeSort(left), mergeSort(right))
  }
}

Tail recursive merge

def mergeSort[T](list: List[T])(implicit ordering: Ordering[T]): List[T] = {
  def merge(l: List[T], r: List[T], finish: List[T]): List[T] =
    (l, r) match {
      case (lHead:: lTail, rHead :: rTail) if ordering.lteq(lHead, rHead) => merge(lTail, r, finish :+ lHead)

      case (lHead:: lTail, rHead :: rTail) => merge(l, rTail, finish :+ rHead)

      case (x, Nil) => finish ++ x

      case (Nil, y) => finish ++ y

      case (Nil, Nil) => finish
    }

  val halfway = list.length / 2
  if (halfway == 0) list  // list is empty or list is single value
  else {
    val (left, right) = list.splitAt(halfway)
    merge(mergeSort(left), mergeSort(right), Nil)
  }
}