scala--使用List编写归并排序
本文给出编写归并排序的一种方法，哈哈，还是包含很多信息的，你来细细品。
下面这个归并排序的实现，真的好优雅，看的人舒心，让自己也想写出这样的代码。
采用了模式匹配，柯里化和递归：
// 归并排序def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {def merge(xs: List[T], ys: List[T]): List[T] =(xs, ys) match {case (Nil, _) => yscase (_, Nil) => xscase (x :: xs1, y :: ys1) => if (less(x, y)) x :: merge(xs1, ys) else y :: merge(xs, ys1)}val n = xs.length / 2if (n == 0) xselse {val (ys, zs) = xs splitAt nmerge(msort(less)(ys), msort(less)(zs))}}scala> msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))res31: List[Int] = List(1, 3, 5, 7)
对于后面的调用时，为啥要 (x: Int, y: Int) => x < y 带上类型声明，这个涉及到scala的类型推断。简单来说就是编译器按照参数列表的第一个来推测数据的类型。
scala> msort(_ > _)(abcde)<console>:12: error: missing parameter type for expandedfunction ((x$1, x$2) => x$1.$greater(x$2))msort(_ > _)(abcde)scala> msort[Char](_ > _)(abcde)res68: List[Char] = List(e, d, c, b, a)// 可以把给出类型的放到前面，这样就可以用占位符啦。def msortSwapped[T](xs: List[T])(less:(T, T) => Boolean): List[T] = {// same implementation as msort,// but with arguments swapped}scala> msortSwapped(abcde)(_ > _)res69: List[Char] = List(e, d, c, b, a)
用scala来写算法，真的其乐无穷，欢迎读者自己来探索如何发挥scala的语法特性来写出简洁高效优雅的代码。
可以阅读下面这本书中的问题，自己来边解决问题边练习熟练使用scala的语法特性。