scala函数快速排序

Question

本书第2章http://www.scala-lang.org/docu/files/ScalaByExample.pdf，M.Odersky写了以下快速分拣的实现

def sort(xs: Array[Int]): Array[Int] = {
 if (xs.length <= 1) xs
 else {
 val pivot = xs(xs.length / 2)
  Array.concat(
   sort(xs filter (pivot >)),
   xs filter (pivot ==),
   sort(xs filter (pivot <)))
 }
}

并表示"命令和功能实现具有相同的渐近性复杂性–平均情况下为O（N log（N））"但看起来并不是这样，因为我们为数组分区应用了两次filter谓词。在经典的命令式版本中，我们对数组使用一个循环。那么功能实现的运行时间是O（N log（N））吗？

Answer 1

filter本身有O（n）和O（3n）=O（n，因为3是一个常数因子。不管n有多大，filter只会被调用3次。

edit：过滤器被调用3次

Answer 2

Quicksort和许多其他分而治之算法的工作方式是，在不超过O(log(n))的数据传递中，最多执行O(n)的工作。在每一步中，我们都将数据大致一分为二，这意味着我们确实只有log2(n)通过数据（一个没有被分割，一个大致被分割，等等）

然后，您只需要检查每次通过数据所花费的时间是否不超过O(n)。滤波器为O(n)，我们滤波三次；加上concat就是O(n)，我们做一次。因此我们做了4*O(n)的工作，也就是O(n)。

这不是最有效的算法，因为所有的传递都是相同的数据，但它的顺序是正确的。