object QuickSort {

  val list = List(1,9,2,8,3,7,4,6,5);

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

  def main(args: Array[String]) {
    val res = qsort(list)
    res.foreach(print)
  }
}