QuickSort in Scala

Today I stumbled on this post, showing Quick-Sort impl in various languages.. and I got the itch to impl a simple version for same in scala. Here is the result..

def quickSort[A](xs: List[A])(implicit orderer:(A)=>Ordered[A]): List[A] =
  xs match {
    case Nil => xs
    case _ :: Nil => xs
    case x :: rest =>
      quickSort(rest.filter(orderer(_) <= x)) ++ List(x) ++ 
      quickSort(rest.filter(orderer(_) > x))
  }

Interesting thing to note is that the size is close to same as the Haskell impl in the mentioned post.

A trial run on the Scala REPL..

Welcome to Scala version 2.7.5.final (Java HotSpot(TM) Client VM, Java 1.6.0_07).
Type in expressions to have them evaluated.
Type :help for more information.

scala> def quickSort[A](xs: List[A])(implicit orderer:(A)=>Ordered[A]): List[A] =
  xs match {
    case Nil => xs
    case x :: Nil => xs
    case x :: rest =>
      quickSort(rest.filter(orderer(_) <= x)) ++ List(x) ++ quickSort(rest.filter(orderer(_) > x))
  }
     |      |      |      |      |      | quickSort: [A](List[A])(implicit (A) => Ordered[A])List[A]

scala> quickSort(List(2,2,2,100,-1,2,5,1,0,3,4,3))
res0: List[Int] = List(-1, 0, 1, 2, 2, 2, 2, 3, 3, 4, 5, 100)

scala> quickSort(List("himanshu","ruchi","nitin","manoj"))
res1: List[java.lang.String] = List(himanshu, manoj, nitin, ruchi)