Not only is it making two-passes for filtering, it also has to do another pass to append "lesser" onto [p] and "greater". And that is for a single recursion so these multiple passes are happening per-recursive call.

Here's a page with some actual haskell quicksorts:

http://www.haskell.org/haskellwiki/Introduction/Direct_Trans...