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

[Duncan Coutts]

On Sun, 2008-03-09 at 23:04 -0400, Dan Doel wrote:
> On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:

> > What do you think about this particular function?
> 
> 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.
> 
> 3) I imagine the time taken to get any output is always O(n*log n). Various 
> lazy sorts can be written (and I'd guess the standard library sort is written 
> this way, although I don't know for sure) such that 'head (sort l)' is O(n), 
> or O(n + k*log n) for getting the first k elements. However, Map, being a 
> balanced binary tree, doesn't (I think) have the right characteristics for 
> this.

Sounds to me like we should try a heap sort. As a data structure it
should have similar constant factors to Data.Map (or .Set) but a heap is
less ordered than a search tree and gives the O(n + k*log n) property.

Duncan