quicksort.scala

import scala.util.Random.nextInt

def choosePivot(xs: List[Int]): Int = {
  if (xs.isEmpty) 0
  else xs(nextInt(xs.length))
}

def quicksort(xs: List[Int], p: Int): List[Int] = {
  if (xs.isEmpty) List()
  else if (xs.length == 1) xs
  else {
    val ys: (List[Int], List[Int]) = xs.partition(_ < p)
    quicksort(ys._1, choosePivot(ys._1)) ::: quicksort(ys._2, choosePivot(ys._2))
  }
}

val xs = List(4,2,9,1,3,6)
println(quicksort(xs, choosePivot(xs)))