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?
