# [Haskell-cafe] Re: (flawed?) benchmark : sort

Don Stewart dons at galois.com
Sun Mar 9 23:08:32 EDT 2008

```dan.doel:
> On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:
> > Ok, I did some search and found Data.Map, which can be used to implement
> > pretty fast sorting:
> >
> > import qualified Data.Map as Map
> >
> > treeSort :: Ord a => [a] -> [a]
> > treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map
> > (\x->(x,()))
> >
> > In fact It is likely to behave like sort, with the exception that it is 23%
> > faster. I did not hovever check the memory consumption. It works well on
> > random, sorted and reverse-sorted inputs, and the speed difference is
> > always about the same. I belive I could take Data.Map and get datatype
> > isomorphic to specialized *Data.Map a ()* of it, so that treeSort will
> > became Map.toAscList . Map.fromList. This may also bring some speedup.
> >
>
> Some thoughts:
>
> 1) To get your function specifically, you could just use Data.Set.Set a
> instead of Map a ().
>
> 2) What does it do with duplicate elements in the list? I expect it deletes
> them. To avoid this, you'd need to use something like fromListWith, keeping
> track of how many duplicates there are, and expanding at the end.

And a little QuickCheck to help things along:

import qualified Data.Map as Map
import Data.List
import Test.QuickCheck

treeSort :: Ord a => [a] -> [a]
treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map (\x->(x,()))

main = quickCheck prop_sort

prop_sort xs = sort xs == treeSort xs
where _ = xs :: [Int]

Running: