Duncan Coutts wrote: > 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. Thanks to lazyness, mergesort is really a heapsort in disguise. Regards, apfelmus