How do you write an idiomatic Scala Quicksort function?
- by Don Mackenzie
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.
