How do you write an idiomatic Scala Quicksort function?

Question

I recently answered a question with an attempt at writing a quicksort function in scala, I'd seen something like the code below written somewhere.

def qsort(l: List[Int]): List[Int] = {
  l match {
    case Nil         => Nil
    case pivot::tail => qsort(tail.filter(_ < pivot)) ::: pivot :: qsort(tail.filter(_ >= pivot))
  }
}

My answer received some constructive criticism pointing out that List was a poor choice of collection for quicksort and secondly that the above wasn't tail recursive.

I tried to re-write the above in a tail recursive manner but didn't have much luck. Is it possible to write a tail recursive quicksort? or, if not, how can it be done in a functional style? Also what can be done to maximise the efficiency of the implementation?

Thanks in advance.

Answer 1

A few years back, I spent some time trying to optimize functional quicksort as far as I could. The following is what I came up with for vanilla List[A]:

def qsort[A : Ordering](ls: List[A]) = {
  import Ordered._

  def sort(ls: List[A])(parent: List[A]): List[A] = {
    if (ls.size <= 1) ls ::: parent else {
      val pivot = ls.head

      val (less, equal, greater) = ls.foldLeft((List[A](), List[A](), List[A]())) {
        case ((less, equal, greater), e) => {
          if (e < pivot)
            (e :: less, equal, greater)
          else if (e == pivot)
            (less, e :: equal, greater)
          else
            (less, equal, e :: greater)
        }
      }

      sort(less)(equal ::: sort(greater)(parent))
    }
  }
  sort(ls)(Nil)
}

I was able to do even better with a custom List structure. This custom structure basically tracked the ideal (or nearly ideal) pivot point for the list. Thus, I could obtain a far better pivot point in constant time, simply by accessing this special list property. In practice, this did quite a bit better than the standard functional approach of choosing the head.

As it is, the above is still pretty snappy. It's "half" tail recursive (you can't do a tail-recursive quicksort without getting really ugly). More importantly, it rebuilds from the tail end first, so that results in substantially fewer intermediate lists than the conventional approach.

It's important to note that this is not the most elegant or most idiomatic way to do quicksort in Scala, it just happens to work very well. You will probably have more success writing merge sort, which is usually a much faster algorithm when implemented in functional languages (not to mention much cleaner).

Answer 2

I guess it depends on what do you mean by "idiomatic". The main advantage of quicksort is being a very fast in-place sorting algorithm. So, if you can't sort in-place, you loose all its advantages -- but you're still stuck with it's dis advantages.

So, here's some code I wrote for Rosetta Code on this very subject. It still doesn't sort in-place, but, on the other hand, it sorts any of the new collections:

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom
def quicksort
  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]      // My type parameters -- which are expected to be inferred
  (coll: CC[T])                                                    // My explicit parameter -- the one users will actually see
  (implicit ord: Ordering[T], cbf: CanBuildFrom[CC[T], T, CC[T]])  // My implicit parameters -- which will hopefully be implicitly available
  : CC[T] =                                                        // My return type -- which is the very same type of the collection received
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll.tail partition (ord.lt(_, coll.head))
    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
  }