On Thu, Jan 22, 2015 at 02:29:58PM -0800, Andrei Alexandrescu via Digitalmars-d wrote: [...] > Thanks. I'm thinking of something based on general comparisons. > Something like a modified quicksort with fat pivot: > > A. Partition into three subranges: R1<pivot, R2=pivot, R3>pivot > > B. Recurse on R1 obtaining R11, a subrange of R1 containing only > unique elements. > > C. Sort-move-unique R2 into the portion after R11, obtaining the > result. > > A and B seem fine, I'm unclear about C. It would be an algorithm that > sorts and simultaneously moves data in a range that overlaps the > input. [...]
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]. T -- Famous last words: I wonder what will happen if I do *this*...
