title: QuickSort Traditional vs Functional Style What Causes This Difference?
body: <p>I am comparing two codes written in scala language. </p>
  
  <pre><code>package chapter01
  
  object QuickSortScalaTime {
    def sortFunctional(xs: Array[Int]): Array[Int] = {
      if (xs.length &lt;= 1) xs
      else {
        val pivot = xs(xs.length / 2)
        Array.concat(sortFunctional(xs filter (pivot &gt;)), xs filter (pivot ==), sortFunctional(xs filter (pivot &lt;)))
      }
    }
  
    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 &lt;= j) {
          while (xs(i) &lt; pivot) i += 1
          while (xs(j) &gt; pivot) j -= 1
          if (i &lt;= j) {
            swap(i, j)
            i += 1
            j -= 1
          }
        }
        if (l &lt; j) sort1(l, j)
        if (j &lt; 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))
    }
  
  }
  </code></pre>
  
  <p>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. </p>
  
  <p>There is a huge difference between traditional and functional. </p>
  
  <pre><code>Functional style : 450
  Traditional style : 30
  </code></pre>
  
  <p>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 ?</p>