Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 3 / g

A compatible Ord instance supplies a total order, so use comparison sort to put equal values together in $O(n\log n)$ time and then group adjacent equals in linear time. To preserve the first-occurrence group ordering of part (f), first tag every element with its original index and stable sorting by value. Group the sorted records by value; stability preserves their internal input order. Each group's first record carries its smallest original index. Sort the groups by that index and finally remove the tags. The second sort has at most $n$ records, so the total remains $O(n\log n)$ time and $O(n)$ storage. Merely returning the value-sorted groups could reorder the classes, so the index step matters when preserving the exact earlier convention. The stronger interface evades the equality-only lower bound by permitting order comparisons.