For clarity: if tests were to feed your solution an input with an Eq instance but not an Ord instance, it would fail. So you are not implementing the specs fully; you are too restrictive.

In short: no, but tests are inadequate, so yes.

To me it feels like rewriting the problem. Maybe the test spec should feed a list of a custom datatype with only Eq instance.

is it ok to add an "Ord a" constraint?

Each length is calculated twice, so I can't even tell without testing if caching would help or not. And the complexity is just O(n * log n), the group lengths are not independent of the list length, they are made of the same items.

It has approximate time complexity O(n log n). ( I already thought so. But I checked. ) Your C or assembly solution might have time complexity O(n), but will very, very probably also have O(n log n).

No, length is not cached. But even without, time complexity is something like (O m n log n) with m the length of the longest group. That's approximately a small constant except in extreme cases. Caching length would be a good thing here.

This is probably the most efficient, no?