title: which algorithm can do a stable in-place binary partition with only O(N) moves?
body: <p>I'm trying to understand this paper: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.5554">Stable minimum space partitioning
  in linear time.</a></p>
  
  <p>It seems that a critical part of the claim is that </p>
  
  <blockquote>
    <p><strong>Algorithm B</strong> sorts stably a bit-array of size <em>n</em> in
    <em>O(nlog<sub>2</sub>n)</em> time and constant extra space, but makes only <em>O(n)</em> moves.</p>
  </blockquote>
  
  <p>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.   </p>
  
  <p>What is this Algorithm B? In other words, given </p>
  
  <pre><code>boolean Predicate(Item* a);  //returns result of testing *a for some condition
  </code></pre>
  
  <p>is there a function <code>B(Item* a, size_t N);</code> which stably sorts <em>a</em> using <em>Predicate</em> as the sort key with fewer than nlog<sub>2</sub>n calls to Predicate, and performs only O(N) writes to <em>a</em>?</p>