<p>I'm trying to understand this paper: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.5554" rel="nofollow noreferrer">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>The reference is to &quot;<a href="https://link.springer.com/article/10.1007/BF02017344" rel="nofollow noreferrer">Stable in situ sorting and minimum data movement</a>&quot; by J.I. MUNRO, V. RAMAN, et al. Googling reveals that that pair has also published several papers on related topics, including &quot;Fast stable in-place sorting with O(n) data moves. Algorithmica 16, 151–160.&quot; 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.</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 in O(N lg N) time, and performs only O(N) writes to <em>a</em>?</p>
<p><em>I asked this on StackOverflow, I haven't got any good responses.</em></p>

CC BY-SA 2.5
2011-03-31T00:06:59.163Z
I hesitate to describe the algorithm from "stable in situ sorting" because it's quite complicated. The first step in its development is an algorithm that sorts in O(n^2) time with O(n) movement and O(n) extra bits of data. Step 2 is an algorithm that uses step 1 as a subroutine, that sorts in O(n^{3/2}) time with O(n) movement and constant extra space, by first separating out a block of sqrt(n) 0's and another block of sqrt(n) 1's (if not enough of one bit exist then a different special case applied) and using swaps in those two blocks to represent extra bits. Step 3 is recurse.
David Eppstein
CC BY-SA 2.5
2011-03-31T23:11:16.580Z
Am I wrong in understanding that you want a stable in place sort of an array that takes on only two values?
user834
CC BY-SA 2.5
2011-03-31T23:55:24.363Z
The algorithm should work on an array of any arbitrary record type that allows computation of a binary property.  For example, an array of student records already sorted by name, to be partitioned on "grade > 60".  (As opposed to sorting an array which only contains 'X's and 'Y's. )
AShelly
CC BY-SA 2.5
2011-04-01T21:35:45.280Z
@David: I do not know the algorithm, but isn’t your comment the answer to the question?  Since no one should expect the complete description of the algorithm (one has to read the paper for that), I think that a description of the overall structure of the algorithm can be the most useful answer to this question.  (I may be wrong.)
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-04T16:09:20.830Z
@Tsuyoshi Ito, I was going to reply: "Why shouldn't I expect a good description of the algorithm - it is not intended to be a secret, and I can just go to the local library to get a copy of the article if I really wanted it".  Which realization made me go get a copy of the article.  So thank you for that push.
AShelly
CC BY-SA 2.5
2011-04-04T16:21:25.020Z
@David Eppstein.  Thank you for the answer.  If you make the comment an answer, I will accept it.
AShelly
CC BY-SA 2.5
2011-04-04T19:07:39.403Z
@AShelly: Yes, that was my intent.  Thanks for realizing that.
Tsuyoshi Ito
CC BY-SA 4.0
2021-01-15T22:19:05.780Z
@AShelly Just curious, were you able to find an algorithm that satisfies this?
Mathphile
CC BY-SA 4.0
2021-01-16T21:03:32.520Z
The algorithm in the linked paper satisfies it, but I never implemented it - it seemed to be one of those that was efficient in theory but not so much in implementation.  I did implement a linear time partitioning  algorithm here - https://stackoverflow.com/a/5483460/10396, but it's not constant space.
AShelly
<ds.algorithms><space-bounded>
Which algorithm can do a stable in-place binary partition with only O(N) moves?
AShelly
# Which algorithm can do a stable in-place binary partition with only O(N) moves?

(Asked by: username_0 on 2011-03-30)

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.

**Tags:** ds.algorithms, space-bounded

> **Comments:**
> **username_1**: I hesitate to describe the algorithm from "stable in situ sorting" because it's quite complicated. The first step in its development is an algorithm that sorts in O(n^2) time with O(n) movement and O(n) extra bits of data. Step 2 is an algorithm that uses step 1 as a subroutine, that sorts in O(n^{3/2}) time with O(n) movement and constant extra space, by first separating out a block of sqrt(n) 0's and another block of sqrt(n) 1's (if not enough of one bit exist then a different special case applied) and using swaps in those two blocks to represent extra bits. Step 3 is recurse.  
> **username_2**: Am I wrong in understanding that you want a stable in place sort of an array that takes on only two values?  
> **username_0**: The algorithm should work on an array of any arbitrary record type that allows computation of a binary property.  For example, an array of student records already sorted by name, to be partitioned on "grade > 60".  (As opposed to sorting an array which only contains 'X's and 'Y's. )  
> **username_3**: @David: I do not know the algorithm, but isn’t your comment the answer to the question?  Since no one should expect the complete description of the algorithm (one has to read the paper for that), I think that a description of the overall structure of the algorithm can be the most useful answer to this question.  (I may be wrong.)  
> **username_0**: @username_3, I was going to reply: "Why shouldn't I expect a good description of the algorithm - it is not intended to be a secret, and I can just go to the local library to get a copy of the article if I really wanted it".  Which realization made me go get a copy of the article.  So thank you for that push.  
> **username_0**: @username_1.  Thank you for the answer.  If you make the comment an answer, I will accept it.  
> **username_3**: @username_0: Yes, that was my intent.  Thanks for realizing that.  
> **username_4**: @username_0 Just curious, were you able to find an algorithm that satisfies this?  
> **username_0**: The algorithm in the linked paper satisfies it, but I never implemented it - it seemed to be one of those that was efficient in theory but not so much in implementation.  I did implement a linear time partitioning  algorithm here - https://stackoverflow.com/a/5483460/10396, but it's not constant space.  

---

## 0 answers

