quicksort à la LYAHFGG

quicksort.scala

import scala.math.Ordering
import scala.math.Ordering.Implicits._

// https://scastie.scala-lang.org/Yaneeve/msPXA2ThRMqbi8fP6ODl2w
def quicksort[A: Ordering](xs: List[A]): List[A] = xs match {
  case Nil => Nil
  case h :: t => 
  	val smallerThanHead = quicksort(t.filter(_ <= h))
    val greaterThanHead = quicksort(t.filter(_ > h))
    smallerThanHead ::: h :: greaterThanHead
}

quicksort(List(10,2,5,3,1,6,7,4,2,3,4,8,9))

quicksort("the quick brown fox jumps over the lazy dog".toList).mkString