[Haskell-cafe] groupBy without Ord?

[Tom Ellis]

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.