1

The following is a text-book quick sort implementation in Scala. When comparing the execution time of quickSortRecursive to java.util.Arrays.sort(), I found java.util.Arrays.sort to be an order of magnitude faster on large arrays. Can someone hint on the reason for this difference in performance?

def quickSortRecursive(list: Array[Int])(low: Int=0, high: Int=list.length-1): Unit = {
  if (low<high) {
    swap(list,Random.nextInt(high),high)
    val pivot = partition(list, low, high)
    quickSortRecursive(list)(low, pivot-1)
    quickSortRecursive(list)(pivot+1, high)
  }
}

private def partition(list: Array[Int], low: Int, high: Int): Int = {
  val pivot = list(high)
  var lowhigh = low
  for (i <- low until high) {
    if (list(i) < pivot) {
      swap(list, lowhigh, i);
      lowhigh += 1;
    }   
  }
  swap(list, lowhigh, high);
  lowhigh
}

private def swap(list: Array[Int], i: Int, j: Int): Unit = {
  val tmp = list(i)
  list(i) = list(j)
  list(j) = tmp
}
deepkimo
  • 3,187
  • 3
  • 23
  • 21
  • 2
    Because Java [Arrays.sort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28java.lang.Object[]%29) uses a version of [Timsort](http://svn.python.org/projects/python/trunk/Objects/listsort.txt)? – Elliott Frisch May 06 '14 at 02:33
  • 2
    I would retitle your question to make it obvious that this is a "Java vs Scala" question. Also, graph your hand-made Scala sort vs the Java standard library sort for arrays of size around 100 to some size large enough to see an obvious trend, and post that here as well. – Rainbolt May 06 '14 at 02:39
  • 1
    Random.nextInt() is pretty expensive. I would start by removing it. The implementation for `for` loops in scala is relatively complex and not as optimal. – Peter Lawrey May 06 '14 at 02:43
  • @PeterLawrey removing Random.nextInt doesn't change that. In fact, I started without it and added it in case imbalanced trees are an issue. I agree that Scala for loop implementation might be a factor here. – deepkimo May 06 '14 at 02:55
  • 1
    @deepkimo You might be able to step into the code for Scala's for loop to see what it does differently. – Peter Lawrey May 06 '14 at 02:58
  • 2
    As suggested by @AndreasNeumann below, I think that a fair comparison would have you test against the equivalent Java quick sort implementation and not `Arrays.sort`. Otherwise you may first want to check out the implementation details of the latter. – VH-NZZ May 06 '14 at 07:44
  • @ElliottFrisch to clarify Java 7 uses TimSort for objects, but Dual-Pivot Quicksort for primitives http://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort – deepkimo May 07 '14 at 05:14
  • 1
    @deepkimo I actually knew that. It's documented [here](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28int[]%29), and on all the other sort methods. When called from Scala, I think you'll get the `Object[]` one. – Elliott Frisch May 07 '14 at 05:17

1 Answers1

2

You comapared a highly optimized implementation of a generic sorting algorithm (java.util.Arrays.sort) to a handrolled implementation without optimization (your Scala code).

Thus it is bound to be slower.

What result are you aiming for? For a good comparison you could try comparing the different sorting algorithms provided by the Scala standard library against the ones provided by the Java standard disribution. Or you could implement your Quicksort in Java and Scala and compare the results.

Andreas Neumann
  • 10,734
  • 1
  • 32
  • 52
  • 1
    I agree that OP is comparing apples with pears, and was about to also suggest comparing the same hand-written quicksort in Java. – VH-NZZ May 06 '14 at 07:39