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

Thomas Hartman thomas.hartman at db.com
Mon Oct 22 18:44:57 EDT 2007

another point: "deforested" treesort is slower.

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

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.)



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

More information about the Haskell-Cafe mailing list