Stable partition3 implementation

[Timon Gehr via Digitalmars-d]

On 07/11/2015 02:32 AM, Xinok wrote:
> On Friday, 10 July 2015 at 21:26:50 UTC, Timon Gehr wrote:
>> 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.)
>
> log* n grows fast for small inputs,

No, it does not. It has no space to grow. With base e, it is 3 or 4 for 
all input sizes that matter:

http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^8
http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^32
http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^64
http://www.wolframalpha.com/input/?i=IteratedLog%282^2^2^2^2%29

> so we can't simply ignore it.

There is a priori no practical difference between a O(n) algorithm and a 
O(n*log*(n)) algorithm. It all depends on the constants, and it is hence 
not clear-cut that the O(n) algorithm will run faster.

I'm just saying that this should be taken into consideration.

> For example, if n = 2^16 = 65536, then n*lg(n) = 16*2^16 = 2^20 = 1048576.
> ...

The algorithm runs in O(n*log*(n)). It's not n log(n).

>> 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).
>
> I don't know if there is anything relevant but that paper focuses on a
> different problem involving sorting.

No, it focuses on a few closely related problems, and the 
O(n*log*(n))-algorithms solves a problem that is a straightforward 
generalization of the problem you are looking at. Stable three way 
partition is stable sorting where there are only three "distinct" values 
(smaller, equal, greater). The paper you provided builds on top of this 
algorithm. It is the main reference and part (ii) of the "Algorithm B" 
part of the O(n)/O(1) algorithm does not occur in the paper you 
provided, but only in that other paper, so yes, it is relevant. :-)