<p>The answer by Display name explains why the model trivializes. However, let me add some pointers to established terminology:</p>
<ol>
<li><p>A query-based algorithm is called <strong>nonadaptive</strong> if all the oracle queries are performed independently of the results of the other queries (i.e., essentially in parallel). A comparison sort can be understood as such an algorithm where the queries are comparisons; hence, your static comparison sort model can be called <strong>nonadaptive comparison sort</strong> using standard terminology.</p>
</li>
<li><p>An algorithm is called <strong>oblivious</strong> (or <strong>data-oblivious</strong>, to be precise) if the sequence of operations and memory accesses it performs is independent of the input data (other than its size, I guess). The exact meaning will depend on the set of primitive operations allowed. If you only allow comparisons apart from unconditional moves and arithmetic operations, I suppose you get the same as your model. However, in the literature on oblivious sorting algorithms, it is standard to consider a more powerful model where you can do an atomic <em>compare-and-swap</em> operation (<code>if A&lt;B then swap(A,B)</code>). As a further restriction, <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="noreferrer">sorting networks</a> are a special case of oblivious sorting algorithms where in-place compare-and-swap operations on cells of the input array are the <em>only</em> allowed operations. As noted in the Wikipedia article, there are several practical sorting networks of depth <span class="math-container">$O((\log n)^2)$</span> (and thus with <span class="math-container">$O(n(\log n)^2)$</span> operations); for theoretical purposes, the AKS network achieves the asymptotically optimal depth <span class="math-container">$O(\log n)$</span> (thus with <span class="math-container">$O(n\log n)$</span> operations), but with astronomical constants. In fact, if we do not care about depth, there do exist even practical sorting network algorithms using <span class="math-container">$O(n\log n)$</span> operations, see <a href="https://arxiv.org/abs/1403.2777" rel="noreferrer">zig-zag sort</a>.</p>
</li>
</ol>

CC BY-SA 4.0
2024-05-21T09:23:01.833Z
2024-05-21T09:23:01.833Z
Emil Jeřábek
<p>The reason this question isn't in the literature is because <span class="math-container">$m = \frac{n(n-1)}{2}.$</span> Suppose we know the order between every element except WLOG, between <span class="math-container">$\sigma(1)$</span> and <span class="math-container">$\sigma(2).$</span> It is impossible to distinguish the permutations <span class="math-container">$e$</span> and <span class="math-container">$(12).$</span></p>
<p>If <span class="math-container">$\sigma(i) &gt; \sigma(j)$</span> is not known, it is impossible to distinguish between the two permutations where <span class="math-container">$\{\sigma(i), \sigma(j)\} = \{n, n-1\}$</span> and the rest are in increasing order: <span class="math-container">$$1, 2, \dots, i-1, n, i+1, \dots, j-1, n-1, j+1, \dots$$</span> and <span class="math-container">$$1, 2, \dots, i-1, n-1, i+1, \dots, j-1, n, j+1, \dots$$</span></p>
<p>This could make a nice CS homework problem where you define the terms and ask people what they think about <span class="math-container">$m.$</span></p>

CC BY-SA 4.0
2024-05-21T02:16:07.690Z
2024-05-21T02:16:07.690Z
Display name
<p>Assume all array elements are different. If two items are consecutive in the sorted array, then they must be compared to each other, otherwise we cannot know which one should come first. And since we don’t know which items are consecutive, any two items must be compared. Since comparing a vs b and comparing b vs an are equivalent, we need n(n-1)/2 comparisons.</p>

CC BY-SA 4.0
2024-05-23T07:49:47.853Z
2024-05-23T07:49:47.853Z
gnasher729
<p>In a standard comparison sort, you perform a comparison and your next action is based off of the result of that comparison. What if this was not allowed, and you had to request all the results at the start?</p>
<p>Let <span class="math-container">$[n] = \{1, 2, \dots, n\}.$</span> We say <span class="math-container">$S \subseteq [n]^2$</span> is a static sort if knowing the truth values of <span class="math-container">$\sigma(i) &gt; \sigma(j)$</span> for all <span class="math-container">$(i,j) \in S$</span> uniquely determines a permutation <span class="math-container">$\sigma$</span> of <span class="math-container">$[n].$</span> What is the fastest static sort, i.e. what is <span class="math-container">$m := \min |S|$</span>? Clearly, <span class="math-container">$$n\log_2(n) - n \le m \le \frac{n(n-1)}{2}.$$</span></p>
<p>I assume this question has already been studied and answered, but I couldn't find it. Presumably, whoever answered it is using different terminology and unless I know their term for &quot;static sort,&quot; I won't find their paper.</p>
<p>Meta question: how do I find results like this when I don't know how the problem could be stated?</p>

<optimization><sorting>
What is the fastest static comparison sort? What is the proper term for "static"?
Display name
# What is the fastest static comparison sort? What is the proper term for "static"?

(Asked by: username_0 on 2024-05-21)

In a standard comparison sort, you perform a comparison and your next action is based off of the result of that comparison. What if this was not allowed, and you had to request all the results at the start?

Let $[n] = \{1, 2, \dots, n\}.$ We say $S \subseteq [n]^2$ is a static sort if knowing the truth values of $\sigma(i) > \sigma(j)$ for all $(i,j) \in S$ uniquely determines a permutation $\sigma$ of $[n].$ What is the fastest static sort, i.e. what is $m := \min |S|$? Clearly, $$n\log\_2(n) - n \le m \le \frac{n(n-1)}{2}.$$

I assume this question has already been studied and answered, but I couldn't find it. Presumably, whoever answered it is using different terminology and unless I know their term for "static sort," I won't find their paper.

Meta question: how do I find results like this when I don't know how the problem could be stated?

**Tags:** optimization, sorting


---

## 3 answers

### Answer by username_1 on 2024-05-21. Score: 11

The answer by username_0 explains why the model trivializes. However, let me add some pointers to established terminology:

1. A query-based algorithm is called **nonadaptive** if all the oracle queries are performed independently of the results of the other queries (i.e., essentially in parallel). A comparison sort can be understood as such an algorithm where the queries are comparisons; hence, your static comparison sort model can be called **nonadaptive comparison sort** using standard terminology.
2. An algorithm is called **oblivious** (or **data-oblivious**, to be precise) if the sequence of operations and memory accesses it performs is independent of the input data (other than its size, I guess). The exact meaning will depend on the set of primitive operations allowed. If you only allow comparisons apart from unconditional moves and arithmetic operations, I suppose you get the same as your model. However, in the literature on oblivious sorting algorithms, it is standard to consider a more powerful model where you can do an atomic *compare-and-swap* operation (`if A). As a further restriction, sorting networks are a special case of oblivious sorting algorithms where in-place compare-and-swap operations on cells of the input array are the only allowed operations. As noted in the Wikipedia article, there are several practical sorting networks of depth $O((\log n)^2)$ (and thus with $O(n(\log n)^2)$ operations); for theoretical purposes, the AKS network achieves the asymptotically optimal depth $O(\log n)$ (thus with $O(n\log n)$ operations), but with astronomical constants. In fact, if we do not care about depth, there do exist even practical sorting network algorithms using $O(n\log n)$ operations, see zig-zag sort.`


---

### Answer by username_0 on 2024-05-21. Score: 7

The reason this question isn't in the literature is because $m = \frac{n(n-1)}{2}.$ Suppose we know the order between every element except WLOG, between $\sigma(1)$ and $\sigma(2).$ It is impossible to distinguish the permutations $e$ and $(12).$

If $\sigma(i) > \sigma(j)$ is not known, it is impossible to distinguish between the two permutations where $\{\sigma(i), \sigma(j)\} = \{n, n-1\}$ and the rest are in increasing order: $$1, 2, \dots, i-1, n, i+1, \dots, j-1, n-1, j+1, \dots$$ and $$1, 2, \dots, i-1, n-1, i+1, \dots, j-1, n, j+1, \dots$$

This could make a nice CS homework problem where you define the terms and ask people what they think about $m.$


---

### Answer by username_2 on 2024-05-23. Score: 2

Assume all array elements are different. If two items are consecutive in the sorted array, then they must be compared to each other, otherwise we cannot know which one should come first. And since we don’t know which items are consecutive, any two items must be compared. Since comparing a vs b and comparing b vs an are equivalent, we need n(n-1)/2 comparisons.


---

