Scala: Merge sort for lists of type T, parametrisation, polymorphism, comparison operation and implicit parametres

merge_sort2.scala

// We want to be able to sort on lists of any type.
// PARAMETRISATION OF SORT: The most flexible design is to make
// the function polymorphic and to pass the comparison operation
// as an additional parametre
def msort[T](xs: List[T])(lt: (T, T) => Boolean) = {
  val n = xs.length / 2
  if (n == 0) xs
  else {
    def merge(xs: List[T], ys: List[T]) = ???
    val (fst, snd) = xs splitAt n
    merge(msort(fst)(lt), msort(snd)(lt))
  }
}

// And merge would be
def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
  ...
  case (x :: xs1, y :: ys1) =>
    if (lt(x, y)) ...
    else ...
}

// This is the way we can call these functions
val nums = List(2, -4, 5, 7, 1)
msort(nums)((x, y) => x < y) // Compiler can infer types here
val fruits = List("apple", "pineapple", "orange")
msort(fruits)((x: Int, y: Int) => x.compareTo(y) < 0)

// BUT: There is already a scala.mathOrdering[T] class in Scala!
def msort[T](xs: List[T])(ord: Ordering[T]) = { ... } // <== ord: Ordering[T]
def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
  ...
  case (x :: xs1, y :: ys1) =>
    if (ord.lt(x, y)) ... // <== ord.lt used here
    else ...
}
msort(nums)(Ordering.Int) // <== Predefined Int ordering chosen
msort(fruits)(Ordering.String) // <== Predefined String ordering chosen

// One step further
// If we use 'implicit' the compiler tries to look for an 'ord' definition that:
// * Is marked implicit
// * has a type compatible with T
// * is visible at the point of the function call,
//   or is defined in a companion object associated with T
def msort[T](xs: List[T])(implicit ord: Ordering[T]) = { ... } // <== implicit!
def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
  ...
  case (x :: xs1, y :: ys1) =>
    if (ord.lt(x, y)) ... // <== Same as before
    else ...
}
msort(nums) // <== No need to be explicit about the ordering
msort(fruits) // <== Idem