Scala编程之归并排序

       在排序算法中，归并排序比插入排序的效率更高，下面通过Scala语言实现归并排序。

/**
  * Created by user on 2016/1/22.
  */
object MergeSort {
   def mergeSort[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, _) => 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)
        merge(mergeSort(less)(ys),mergeSort(less)(zs))
     }
   }

   def main(args: Array[String]) {
      val flag = (x: Int, y:Int) => x < y
      val num = List(2, 1, 4, 3, 5, 7, 0)
      println("Merge Sort: " + mergeSort(flag)(num))
   }
}

 测试结果如下所示：

       Merge Sort: List(0, 1, 2, 3, 4, 5, 7)