# [Haskell-cafe] will the real quicksort please stand up? (or: sorting a > million element list)

jerzy.karczmarczuk at info.unicaen.fr jerzy.karczmarczuk at info.unicaen.fr
Mon Oct 22 19:30:10 EDT 2007

```Thomas Hartman writes:

> another point: "deforested" treesort is slower.
> The commented indicated that
>
> -- If you deforest this algorithm (removing the intermediate tree
> structure) you are left with
> treeSort' [] = []
> treeSort' (x:xs) = treeSort' (filter (<= x) xs) ++ [x] ++ treeSort'
> (filter (x <) xs)
>
> So.. my take home lesson is that deforestation isn't a performance neutral
> thing to do. Assuming the comment is correct.

Well this was just the removal of the auxiliary *tree* formulae, but such
recursive concatenation isn't anything which should be popularized...
I don't want to start an analysis of known issues, but if you WANT to have
*similar* algorithms relatively efficient, there are two things to do:
1. Avoid two pass filtering.
2. Avoid unecessary (++), with an accumulator. For example:

qsort l = qs l [] where    -- pa is the one-pass partition
qs (x:xs) ac = pa xs [] [] where
pa (y:ys) s b | x<y = pa ys s (y:b)
| otherwise = pa ys (y:s) b
pa [] s b = qs s (x:qs b ac)   -- s- small; b- big; ac- buffer
qs [] ac = ac

Jerzy Karczmarczuk

```