sortUniq

[H. S. Teoh via Digitalmars-d]

On Thu, Jan 22, 2015 at 02:29:58PM -0800, Andrei Alexandrescu via Digitalmars-d wrote:
[...]
> Thanks. I'm thinking of something based on general comparisons.
> Something like a modified quicksort with fat pivot:
> 
> A. Partition into three subranges: R1<pivot, R2=pivot, R3>pivot
> 
> B. Recurse on R1 obtaining R11, a subrange of R1 containing only
> unique elements.
> 
> C. Sort-move-unique R2 into the portion after R11, obtaining the
> result.
> 
> A and B seem fine, I'm unclear about C. It would be an algorithm that
> sorts and simultaneously moves data in a range that overlaps the
> input.
[...]

Wait, if R1 and R3, after the recursion, are sorted and contain only
unique elements, doesn't that mean that we can just collapse R2 into a
single element along with the endpoints of R1 and R3? So if R1[$-1] <
pivot, then we're done, otherwise coalesce it with the pivot, and
likewise with R3[0].


T

-- 
Famous last words: I wonder what will happen if I do *this*...