Stable partition3 implementation

[Andrei Alexandrescu via Digitalmars-d]

On 7/9/15 5:57 PM, Xinok wrote:
> I wanted to get some feedback on a stable partition3 implementation for
> Phobos before I work on a pull request. I wrote this implementation
> which is in-place (zero memory allocations) but runs in O(n lg n) time.
>
> http://dpaste.dzfl.pl/e12f50ad947d
>
> I found this paper which describes an in-place algorithm with O(n) time
> complexity but it's over my head at the moment.
>
> http://link.springer.com/article/10.1007%2FBF01994842
>
> It is trivial to implement an algorithm with O(n) time complexity and
> O(n) space complexity, but that requires allocating memory. Furthermore,
> using a buffer requires the range to have assignable elements.
>
>
> Any thoughts?

I'd say both would be nice (not to mention the one in the paper) so how 
about both are present selectable with a policy ala Yes.tightMemory or 
something. -- Andrei