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.