That's right. That Haskell faux-quicksort uses a lot of extra space for the temporary lists.

Here's a Haskell version of the "real" quicksort, though it isn't nearly easy a read as the faux-quicksort:

http://augustss.blogspot.jp/2007/08/quicksort-in-haskell-qui...

For what is worth, the standard Haskell sort is a variant of merge sort.

http://hackage.haskell.org/packages/archive/base/latest/doc/...