[Haskell-cafe] groupBy without Ord?

[martin]

Am 03/30/2014 11:15 PM, schrieb Tom Ellis:


>>  groupEq :: Eq a => [a] -> [[a]]
>>  groupEq [] = []
>>  groupEq (a:rest) = (a:as) : groupEq bs
>>    where (as,bs) = partition (==a) rest
> 
> This is O(n^2).

I understood, that you suggested to go ahead and sort the list, instead of just aligning equal elements next to each
other. So far all my attempts to prove you wrong failed.

But I still have trouble to believe, that sorting (Ord=>) is cheaper than aligning (Eq=>) because sorting does aligning
plus some more. Does (Ord=>) make life so much easier, or why do you think this is the case?