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

CC BY-SA 4.0
2022-08-20T22:58:23.670Z
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(log2n) bits, is available". O(log n / log log n) **counters** is still clearly not a constant number of counters.
Mathphile
CC BY-SA 4.0
2022-08-20T23:07:54.943Z
I guess this further leads to the question: Does an algorithm exist that can stably sort a binary array in O(n) time and O(1) space with a **constant** number of storage locations?
Mathphile
CC BY-SA 4.0
2022-08-22T16:08:01.373Z
@Mathphile But they do use a constant number of storage locations:  The extra counters are emulated using those locations and bit shift operations.
Dmytro Taranovsky
CC BY-SA 4.0
2022-07-20T13:55:04.570Z
2022-07-20T13:55:04.570Z
Dmytro Taranovsky
<p>The paper <a href="http://hjemmesider.diku.dk/%7Ejyrki/Paper/KP1992bJ.pdf" rel="nofollow noreferrer">Stable Minimum Space Partitioning in Linear Time</a> describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in <span class="math-container">$O(n)$</span> time complexity and <span class="math-container">$O(1)$</span> space complexity. After reading the paper, I am not really convinced that the algorithm described is actually <span class="math-container">$O(1)$</span> space complexity which is one of the main selling points of the algorithm that distinguishes it from other partitioning algorithms.</p>
<p>Although the algorithm uses constant memory (technically it is <span class="math-container">$O(\log n)$</span> bits, but we can consider it <span class="math-container">$O(1)$</span> in practical use), it doesn't use <span class="math-container">$O(1)$</span> counters. The authors define <span class="math-container">$O(1)$</span> space as &quot;we assume that a constant number of extra storage locations, each capable for storing a word of <span class="math-container">$O(\log_2 n)$</span> bits, is available&quot; (page 2). But later in algorithm D, the authors clearly use <span class="math-container">$O(\log(n)/\log(\log(n)))$</span> counters thereby contradicting their earlier statement of <span class="math-container">$O(1)$</span> space complexity.</p>
<p>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 <span class="math-container">$O(\log_2 n)$</span> 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.</p>
<p>Is the algorithm indeed not <span class="math-container">$O(1)$</span> space complexity, or am I misunderstanding the paper somehow?</p>

<ds.algorithms><space-complexity>
Problem in the paper "Stable Minimum Space Partitioning in Linear Time"
Mathphile
# Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

(Asked by: username_0 on 2021-07-27)

The paper [Stable Minimum Space Partitioning in Linear Time](http://hjemmesider.diku.dk/%7Ejyrki/Paper/KP1992bJ.pdf) 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?

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

---

## 1 answers

### Answer by username_1 on 2022-07-20. Score: 2

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](https://cstheory.stackexchange.com/questions/51722/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.

> **Comments:**
> **username_0**: 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(log2n) bits, is available". O(log n / log log n) **counters** is still clearly not a constant number of counters.  
> **username_0**: I guess this further leads to the question: Does an algorithm exist that can stably sort a binary array in O(n) time and O(1) space with a **constant** number of storage locations?  
> **username_1**: @Mathphile But they do use a constant number of storage locations:  The extra counters are emulated using those locations and bit shift operations.  

---

