I'm trying to understand this paper: Stable minimum space partitioning in linear time.
It seems that a critical part of the claim is that
Algorithm B sorts stably a bit-array of size n in O(nlog2n) time and constant extra space, but makes only O(n) moves.
However, the paper doesn't describe the algorithm, but only references another paper which I don't have access to. I can find several ways to do the sort within the time bounds, but I'm having trouble finding one that guarantees O(N) moves without also requiring more than constant space.
The reference is to "Stable in situ sorting and minimum data movement" by J.I. MUNRO, V. RAMAN, et al. Googling reveals that that pair has also published several papers on related topics, including "Fast stable in-place sorting with O(n) data moves. Algorithmica 16, 151–160." So I think it is a real technique (at least in theory). But I've been unable to figure out how to create a working version.
What is this Algorithm B? In other words, given
boolean Predicate(Item* a); //returns result of testing *a for some condition
is there a function
B(Item* a, size_t N); which stably sorts a using Predicate as the sort key in O(N lg N) time, and performs only O(N) writes to a?
I asked this on StackOverflow, I haven't got any good responses.