Stable partition3 implementation

[Xinok via Digitalmars-d]

On Saturday, 11 July 2015 at 00:00:47 UTC, Andrei Alexandrescu 
wrote:
> On 7/9/15 5:57 PM, Xinok wrote:
>> ...
>>
>> 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

I'm hesitant to add yet another template parameter; IMHO, it's 
bad enough that we have to manually write the predicate just to 
reach the swap strategy.

There's a fourth option I didn't think to mention. It's easy to 
utilize a small buffer which would be used to partition small 
sublists instead of insertions. partition3 would not allocate 
it's own memory so would be in-place by default, but the user 
could provide their own buffer and pass it as an extra function 
argument. For example:

     int[] arr = iota(0, 100000).array;
     int[] buf = new int[100];
     partition3!(...)(arr, 1000, buf);

Interestingly, for some constant k, if you implement this 
algorithm to use O(n/k) space, then it runs in O(n lg n) time 
because it performs at most O(lg k) rotations.

Regarding the algorithm in the paper, I don't have it completely 
figured out yet because it refers to algorithms in other papers 
which I can't find.