I am trying to understand the Scala quicksort example from Wikipedia. How could the sample be disassembled step by step and what does all the syntactic sugar involved mean?

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

As much as I can gather at this stage qsort is a function that takes no parameters and returns a new Function1[List[Int],List[Int]] that implements quicksort through usage of pattern matching, list manipulation and recursive calls. But I can't quite figure out where the pivot comes from, and how exactly the pattern matching syntax works in this case.

UPDATE:

Thanks everyone for the great explanations!

I just wanted to share another example of quicksort implementation which I have discovered in the Scala by Example by Martin Odersky. Although based around arrays instead of lists and less of a show-off in terms of varios Scala features I personally find it much less convoluted than its Wikipedia counterpart, and just so much more clear and to the point expression of the underlying algorithm:

def sort(xs: Array[Int]): Array[Int] = {
    if (xs.length <= 1) xs
    else {
        val pivot = xs(xs.length / 2)
        Array.concat(
            sort(xs filter (pivot >)),
            xs filter (pivot ==),
            sort(xs filter (pivot <)))
    }
}
scala
Edit
Report