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.
