 Solution

Choose the first unclassified element as the next equivalence class representative:Assume the Eq instance is an equivalence relation. The stable list partition collects every later occurrence equivalent to x, and rest contains none of that equivalence class. Induction therefore gives exactly one group per class, preserving order within each group and ordering groups by their first occurrence. For $d$ distinct classes, each input element is tested against at most $d$ representatives: the cost is $O(nd)$ and $\Theta (n^2)$ in the all-distinct worst case; a single class takes $\Theta (n)$.

The equality-only grouping lower bound shows that this worst case is unavoidable in the unrestricted equality-oracle model. On an all-distinct input, an untested pair could instead be equal without changing any observed comparison. Certifying that all $n$ elements belong to different classes therefore requires all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairwise equality tests.