Proposal: Add Data.List.sortNub and sortNubBy

Ketil Malde ketil+haskell at
Wed Mar 14 04:07:44 EDT 2007

"Neil Mitchell" <ndmitchell at> writes:

> nub will be O(#in * #out). Sort will be O(#in log #in). Where #out is
> much smaller than log #in, nub will win.

This can be remedied by having (quick)sort partitioning in three
groups (less than, equal to, and greater than the pivot).  I think I
argued that this should be the default, since it reduces a category of
bad-case behaviours.

If I haven't seen further, it is by standing in the footprints of giants

More information about the Libraries mailing list