# Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $$O(n)$$ time complexity and $$O(1)$$ space complexity. After reading the paper, I am not really convinced that the algorithm described is actually $$O(1)$$ space complexity which is one of the main selling points of the algorithm that distinguishes it from other partitioning algorithms.

Although the algorithm uses constant memory (technically it is $$O(\log n)$$ bits, but we can consider it $$O(1)$$ in practical use), it doesn't use $$O(1)$$ counters. The authors define $$O(1)$$ space as "we assume that a constant number of extra storage locations, each capable for storing a word of $$O(\log_2 n)$$ bits, is available" (page 2). But later in algorithm D, the authors clearly use $$O(\log(n)/\log(\log(n)))$$ counters thereby contradicting their earlier statement of $$O(1)$$ space complexity.

The reason why having a constant number of counters is important is that, without it, the algorithm most probably wouldn't work out that well in practical use. The algorithm can only have $$O(\log_2 n)$$ extra space if we use a variable number of integer counters that are of variable size. The only way we can have a variable number of integer counters of variable size is if we dynamically allocate them and that would drastically slow down the algorithm, hence making the algorithm impractical.

Is the algorithm indeed not $$O(1)$$ space complexity, or am I misunderstanding the paper somehow?

There is no problem here. The paper (which I was led to by your question) could have been worded better, but the $$O(\log n / \log \log n)$$ counters use $$O(\log \log n)$$ bits each as they are used to sort an array of $$O(\log n)$$ elements.
Their algorithm is not really meant for ordinary practical use: The $$O(1)$$ space requirement leads to a poor constant factor here.
Their algorithm is quite complicated. The question Linear time in-place stable sort (which uses $$O(\log n)$$ bit integer keys instead of just 0 or 1) might help you with the fuller picture.