On Thursday, 22 January 2015 at 21:40:57 UTC, Andrei Alexandrescu
wrote:
There's this classic patter on Unix: |sort|uniq, i.e. sort some
data and only display the unique elements.
What would be a better integrated version - one that does
sorting and uniq in one shot? I suspect the combination could
be quite a bit better than doing the two in sequence.
I think the only way you can go lower than O(n log n) is
pigeonholing (counting sort without the counting), but for
generic keys you need AAs which aren't O(1) (and slow).
Maybe heapsort (you could drop duplicates while building the
heap), but that needs an extra allocation.
- sortUniq Andrei Alexandrescu via Digitalmars-d
-
