scala parameterised merge sort - confusing error message

Question

I am getting a compilation error when calling the (lt: (T,T) => Boolean) function
The error code is "type mismatch; found : x.type (with underlying type T) required: T"
and the x parameter in lt(x,y) is underlined.

object sort {
  def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
    def merge[T](xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x :: xs1, y :: ys1) => {
        if (lt(x, y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
      }
    }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (left, right) = xs splitAt n
      merge(msort(left)(lt), msort(right)(lt))
    }
  }
}

Answer 1

msort and merge have different type parameters. Remove the T type parameter from merge:

def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {

The [T] declares a new parameter unrelated to the first. You get the same error if you declare it as:

def merge[U](xs: List[U], ys: List[U]): List[U] = (xs, ys) match {

lt has a type (U, U) => Boolean, and you're calling it with x and y which have type T and don't match.