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