Stable partition3 implementation

[Xinok via Digitalmars-d]

On Saturday, 11 July 2015 at 02:56:55 UTC, Timon Gehr wrote:
> ...
> The algorithm runs in O(n*log*(n)). It's not n log(n).
> ...

I understand now. I had never heard of an iterated logarithm 
before. I took the asterisk to mean some constant, like a wild 
card if you will. Sorry for the confusion.

I wonder if the true O(n) algorithm is still worth pursuing. 
Although log*(n) may only be a factor of 2 or 3, the O(n) 
algorithm may have a small constant factor which makes it 2-3x 
faster.

>>> 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. :-)

I get that much now, but this paper is still way above my head. 
There's some notation in the sample code that I don't understand. 
In this statement:

e <- #{ j : L[j] = x, 1 <= j <= n }

I'm not sure what the pound # signifies or what exactly is being 
assigned to e. I'm assuming it performs some operation on the 
set, like "max", but I'm not sure what.