sortUniq

[Vladimir Panteleev via Digitalmars-d]

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.