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
