QuickSort Traditional vs Functional Style What Causes This Difference?

Question

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 ?

Answer 1

Well, your functional sort is a bit wrong. It works, but it calls xs.filter three times! So in every call you traverse the list three times, instead of one.

Consider this implementation:

def sort(ls: List[Int]): List[Int] = {
  ls match {
    case Nil => Nil
    case pivot :: tail => {
      val (less, greater) = tail.partition(_ < pivot)
      sort(less) ::: pivot :: sort(greater)
    }
  }
}

I'm not sure it would give you the desired performance, but it avoids unnecessary traversals of the list.

More, you may read the answer described here for an implementation that uses the foldLeft