KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
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 2 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 2 n calls to Predicate, and performs only O(N) writes to a ?
Tags (comma-separated)
Save Edits
Cancel