在本書http://www.scala-lang.org/docu/files/ScalaByExample.pdf的第2章,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))「 但是看起來不是,因爲我們對分區數組應用了兩次謂詞過濾。在經典命令版本中,我們使用一個循環來存儲數組。那麼功能實現O(N log(N))的運行時間是多少?