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

[Thomas Hartman]

another point: "deforested" treesort is slower.

hartthoma at linuxpt:~/ProjectRepos/learning/quicksort>time ghc -e "test 
treeSort' 6" quicksort
1000000

real    4m3.615s
user    1m59.525s
sys     0m0.587s

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. (I don't consider myself 
qualified  to judge.)

t.

---

This e-mail may contain confidential and/or privileged information. If you 
are not the intended recipient (or have received this e-mail in error) 
please notify the sender immediately and destroy this e-mail. Any 
unauthorized copying, disclosure or distribution of the material in this 
e-mail is strictly forbidden.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071022/5591dd48/attachment.htm