Willie Wheeler's personal blog. Mostly tech.

I just ran across the following Haskell quicksort implementation, courtesy of Wikibooks:

```
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
```

This recursive definition is dense but easy to follow. The first line is the base case. In the second line, `x`

is the first element and `xs`

is the rest of the list. Using `x`

as the pivot, we concatenate the sorted lower elements, the pivot and the sorted higher elements.

Here it is in action:

```
ghci> qsort [9,22,1,23,0,-12,3,44,5,4,5,2,44,3,14,15,23]
[-12,0,1,2,3,3,4,5,5,9,14,15,22,23,23,44,44]
```

To be sure, this isn't an optimized implementation. For example, it doesn't choose either a central or a random pivot, so it performs poorly with lists that are already sorted. And it does two passes through the `xs`

at each recursion instead of one.

Still, it's pretty great how the tiny but dense code "captures" quicksort. It's eye-opening to compare it to implementations in other languages.