11
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Mar 31, 2011 at 0:06
  • $\begingroup$ Am I wrong in understanding that you want a stable in place sort of an array that takes on only two values? $\endgroup$
    – user834
    Mar 31, 2011 at 23:11
  • $\begingroup$ 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. ) $\endgroup$
    – AShelly
    Mar 31, 2011 at 23:55
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Tsuyoshi Ito
    Apr 1, 2011 at 21:35
  • 1
    $\begingroup$ @David Eppstein. Thank you for the answer. If you make the comment an answer, I will accept it. $\endgroup$
    – AShelly
    Apr 4, 2011 at 16:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.