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

[jerzy.karczmarczuk at info.unicaen.fr]

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