## Behind the scenes of the good old Quicksort

For some reason, people are fascinated by the concise specification of
quicksort made possible by list comprehensions (the practically minded Haskell
programmer, having done some measurements, will prefer Augustsson's
variant for real-life examples, if it has to be quicksort). So, here is the
variant given on haskell.org, modified so that calls to qsort can be observed:

import Observe
qsort :: [Int] -> [Int]
qsort l = observe "qsort" qsort' l
qsort' [] = []
qsort' (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
main = printO $ qsort [3,4,2,5,1]

Of course, the order of calls to qsort, and the sequence in which
the intermediate structures are observed are just as you expected, right?

Why, then, might this nice code not be the best possible way to write
quicksort in Haskell? Well, here is a hint: We take the same code as
before, but this time annotated to observe calls to (++).

import Observe
import Prelude hiding ((++))
a ++ b = observe "++" (Prelude.++) a b
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
main = printO $ qsort [3,4,2,5,1]

Again, let's see what happens:
Pretty obvious, no? Well, okay, probably not, so in case you've lost
track: the leftmost append is the top-level one, appending the sorted
list of elements greater than or equal to the pivot element to the
end of the result of appending a one-element list with the pivot element
to the end of the sorted list of elements smaller than the pivot element.
But all those operations that are necessary to complete this simple
append! And (not easily visible here) each of those appends walks all through
its left parameter before it can put its second parameter to the end
of (a copy of) the first.