sortUniq

[Vladimir Panteleev via Digitalmars-d]

On Thursday, 22 January 2015 at 23:35:32 UTC, H. S. Teoh via 
Digitalmars-d wrote:
> On Thu, Jan 22, 2015 at 02:51:38PM -0800, H. S. Teoh via 
> Digitalmars-d wrote:
>> 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].

I'm pretty sure that when Andrei said:

>> > C. Sort-move-unique R2 into the portion after R11, obtaining 
>> > the
>> > result.

He meant R3, not R2. R2 is obviously collapsed to one element 
(the pivot).

> Working proof of concept:

I think this will actually have worse performance than sort+uniq, 
since you're now shuffling half of the elements at each recursion 
depth - an additional O(n log n).