= Solution
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 \b[$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.
Back to article page
