sortUniq

[Andrei Alexandrescu via Digitalmars-d]

On 1/22/15 2:51 PM, 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].

Right, forgot to mention the pivot.

You don't recurse on the right, only the left; that way you massage the 
unique stuff in R1 toward the left in the possibly smaller range R11. 
Then the challenge is to sort, uinique-fy, and move in one fell swoop 
from R3 (padded with the pivot to the left) into the portion adjacent to 
R11.

Example: say the range has 100 elements. Then we divide like this:

r[0 .. 30] is <pivot
r[30 .. 34] is =pivot
r[34 .. 100] is >pivot

First, recurse on r[0 .. 30] getting a smaller range that's sorted and 
unique. Say r[0 .. 24].

The step needed now is to take r[33 .. 100], which is ONE copy of the 
pivot plus everything greater than pivot, and in one shot deposit it 
starting at r[24], sorted and uniquefied.

I'm thinking of a modified heapsort that progressively creates the heap 
at r[24], or something like that.



Andrei