big o - which algorithm can do a stable in-place binary partition with only O(N) moves?

Question

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(nlog₂n) 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.

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 with fewer than nlog₂n calls to Predicate, and performs only O(N) writes to a?

Answer 1

I'm tempted to say that it isn't possible. Anytime you're computing O(n log n) amount of information but have (1) nowhere to stash it (constant space), and (2) nowhere to immediately use it (O(n) moves), there is something weird going on, possibly involving heavy use of the stack (which may not be included in the space analysis, although it should be).

It might be possible if you store temporary information inside many bits of just one integer, or something squirrelly like that. (So O(1) in practice, but O(log n) in theory.)

Radix sorting wouldn't quite do it because you'd have to call the predicate to create the digits, and if you don't memoize the transitivity of comparison then you'll call it O(n^2) times. (But to memoize it takes O(log n) amortized space per item, I think.)

QED - Proof by lack of imagination :)