sortUniq

[Andrei Alexandrescu via Digitalmars-d]

On 1/22/15 3:52 PM, Vladimir Panteleev wrote:
> 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).

Yes, thanks and sorry for the distraction.

>> 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).

Yah, the key here is to exploit the combination to get better 
performance than composing the two. So you must do surgery on the core 
algorithms involved.


Andrei