Scala 归并排序

//归并排序
def msort[T](less: (T, T) => Boolean) (xs: List[T]): List[T] = {
  //定义merge方法。对于两个已经有序的集合进行merge，结果也有序。
  def merge(xs: List[T], ys: List[T]): List[T] =
    (xs, ys) match {
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if (less(x, y)) x :: merge(xs1, ys) else y :: merge(xs, ys1)
    }

  //排序逻辑
  val n = xs.length / 2
  if (n == 0) xs
  else {
    val (ys, zs) = xs splitAt n
    //msort对ys进行排序，msort对zs进行排序，两个有序的集合进行merge，最终结果也有序。
    merge(msort(less)(ys), msort(less)(zs))
  }
}