A generic quicksort in Scala

algorithm, scala

Solution

def qsort[T <% Ordered[T]](list: List[T]): List[T] = {
  list match {
  case Nil => Nil     
  case x::xs =>        
    val (before, after) = xs partition (_ < x)
    qsort(before) ++ (x :: qsort(after))
  }
}

Problem

I've been playing around with Scala recently and was thinking about how to implement a generic version of quicksort in it (just to get a better feeling for the language) I came up with something like this ``` object Main { def qs[T](a: List[T], f: (T, T) => Boolean): List[T] = { if (a == Nil) return a val (l, g) = a drop 1 partition (f(a(0),(_:T))) qs(l, f) ::: List(a(0)) ::: qs(g, f) } def main(args: Array[String]): Unit = { val a = List(5,3,2,1,7,8,9,4,6) val qsInt = qs(_: List[Int], (_: Int) > (_: Int)) println(qsInt(a)) } } ``` This is not as generic as I wanted it to be, since I have to explicitly state how to order the elements rather then just doing something like ``` val (l, g) = a drop 1 partition (a(0) >) ``` How can I tell the compiler that T only needs to implement the greater-than operator to be sortable by this function? Regards

Original source