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
