7
$\begingroup$

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?

$\endgroup$

3 Answers 3

11
$\begingroup$

The answer by Display name 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<B then swap(A,B)). 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.

$\endgroup$
0
7
$\begingroup$

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.$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.