[Haskell-cafe] groupBy without Ord?

[Flavio Villanustre]

Martin might have meant merge sort... :)

Flavio

Sent from my iPhone

> On Mar 30, 2014, at 10:12 AM, Tom Ellis <tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> wrote:
> 
>> On Sun, Mar 30, 2014 at 04:06:24PM +0200, martin wrote:
>> Am 03/24/2014 12:34 AM, schrieb John Lato:
>>> I would keep in mind that, given the constraints
>>> 
>>> - you want to group together all equal elements from the entire list
>>> - the only operation you can perform on elements is comparison for equality
>>> 
>>> your function will have quadratic complexity (at least I can't see any way around it).
>> 
>> Wouldn't a modified quicksort give n*log(n) complexity. Something like:
> 
> Quicksort is O(n^2) in the worst case.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe