[Haskell-cafe] groupBy without Ord?

[martin]

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:

groupEq [] = []
groupEq (x:xs) = (groupEq a) ++ [x] ++ (groupEq b)
        where
            a = filter (==x) xs
            b = filter (/= x) xs

This is indeed much slower than the built-in sort, but it slower too whern I replace "==" with ">", resulting in a
texbook quicksort.