QuickSort can't be applied to ArrayBuffer to do sorting In place in Scala

Question

I am little confused with QuickSort in Scala. As per the specification, QuickSort can be applied to only Array, but not to ArrayBuffer. And QuickSort will do the sort in Place i.e. will change the original Array.

val intArray = Array(7,1,4,6,9)           //> intArray  : Array[Int] = Array(7, 1, 4, 6, 9)
Sorting.quickSort(intArray)
intArray.mkString("<"," and ",">")        //> res4: String = <1 and 4 and 6 and 7 and 9>

Now I am not able to understand why the same I can't do with ArrayBuilder. Is there any reason behind this? and If I want to sort an ArrayBuilder with QuickSort Algorithm, what is the option provided by scala? Thanks for all help.

Answer 1

I believe the answer to your question can be found by examining the source code of Scala, to determine just what behavior you can get from the built in functions that come with ArrayBuffer : sortWith, sortBy, etc..

These functions come from defining trait "SeqLike" (you can examine the source code by browsing to that class in ScalaDoc, and clicking the link to next to source:"Seqlike" at the top of the documentation..

Anyhow most of the code related to sorting just gets pushed off this function:

def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
    val len = this.length
    val arr = new ArraySeq[A](len)
    var i = 0
    for (x <- this.seq) {
      arr(i) = x
      i += 1
    }
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
    val b = newBuilder
    b.sizeHint(len)
    for (x <- arr) b += x
    b.result()
  }

Which basically makes a copy of the array and sorts it using Java.util.Arrays.Sort. So the next question becomes, "What is java doing here?" I was curious and the api described:

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

So I think the basic answer is that scala relies heavily on Java's built in quicksorting, and you can make use of any Seq function (sorted, sortWith, sortBy) with better or equal performance to array quicksort functions. You may get a bit of performance hit in the "copy" phase, but classes are just pointers (it's not cloning the objects) so you're not losing much unless you have millions of items.