Stable partition3 implementation

[Timon Gehr via Digitalmars-d]

On 07/09/2015 11:57 PM, Xinok wrote:
> 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 think this method is likely to be less practically relevant than the 
one they improve upon. (log* n really is constant for all practical 
purposes, it is the number of times one needs to iteratively take the 
logarithm until a number below 1 is obtained.)

That paper appears to be available here: 
https://github.com/lispc/lispc.github.com/raw/master/assets/files/situ.pdf

No idea what the constant is though, I have not read the paper (yet).