 Equality-only grouping lower bound

In the comparison model exposing only an equality test between otherwise opaque values, partitioning $n$ values into equivalence classes takes $\Omega (n^2)$ tests in the worst case. Run the algorithm on pairwise distinct values. If any pair remains untested, changing just those two values to equal is consistent with every answer observed so far but changes the required output partition. Every pair must therefore be tested. With a compatible total order, comparison sort can instead group equal values in $O(n\log n)$ time.