QuickSort Traditional vs Functional Style What Causes This Difference?
scala
Solution
It's mentioned in the book:
Both the imperative and the functional implementation have the same asymptotic complexity – O(N log(N)) in the average case and O(N2) in the worst case. But where the imperative implementation operates in place by modifying the argument array, the functional implementation returns a new sorted array and leaves the argument array unchanged. The functional implementation thus requires more transient memory than the imperative one.
The traditional operates in-place on the original array, so no copies are done and no additional memory is needed. The functional one allocates a new array and copies a lot of data on each call.
Problem
I am comparing two codes written in scala language. ``` package chapter01 object QuickSortScalaTime { def sortFunctional(xs: Array[Int]): Array[Int] = { if (xs.length <= 1) xs else { val pivot = xs(xs.length / 2) Array.concat(sortFunctional(xs filter (pivot >)), xs filter (pivot ==), sortFunctional(xs filter (pivot <))) } } def sortTraditionl(xs: Array[Int]) { def swap(i: Int, j: Int) { val t = xs(i); xs(i) = xs(j); xs(j) = t; } def sort1(l: Int, r: Int) { val pivot = xs((l + r) / 2) var i = l; var j = r; while (i <= j) { while (xs(i) < pivot) i += 1 while (xs(j) > pivot) j -= 1 if (i <= j) { swap(i, j) i += 1 j -= 1 } } if (l < j) sort1(l, j) if (j < r) sort1(i, r) } sort1(0, xs.length - 1) } def main(args: Array[String]): Unit = { val arr = Array.fill(100000) { scala.util.Random.nextInt(100000 - 1) } var t1 = System.currentTimeMillis sortFunctional(arr) var t2 = System.currentTimeMillis println("Functional style : " + (t2-t1)) t1 = System.currentTimeMillis sortTraditionl(arr) t2 = System.currentTimeMillis println("Traditional style : " + (t2-t1)) } } ``` The first block is written in functional style and the second block is traditional quick sort. The examples are from Odersky's book by the way. There is a huge difference between traditional and functional. ``` Functional style : 450 Traditional style : 30 ``` I just wonder what causes this difference. I do not know scala in depth but my initial guess is the traditional one uses no mutation and any closures. And what can we do to improve the performance of functional style ?