# Tag Info

### What is the fastest static comparison sort? What is the proper term for "static"?

The answer by Display name explains why the model trivializes. However, let me add some pointers to established terminology: A query-based algorithm is called nonadaptive if all the oracle queries ...
• 17.9k

### What is the fastest static comparison sort? What is the proper term for "static"?

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 ...
• 299

### Is sorting NP-complete?

This is not a full answer, but some partial pieces of information (which you might already be aware of). This is related to the number of linear extensions of the poset. It is known that the worst-...
• 881

### What is the fastest static comparison sort? What is the proper term for "static"?

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 ...
• 127
Accepted

### Can arbitrary comparator be transformed into equivalent key for radix sort?

does for every comparator C(key) exist a function M(key) such that sorting by C gives the same result as radix-sorting by the output of M? SHORT ANSWER Not for non discrete value domains, but yes for ...
• 2,776
1 vote
Accepted

### Algorithm for comparing list elements backwards

Part 1. I found the notation a little confusing. The variable $n$ has repeated in two places. To rephrase the question. Input: A list of real numbers $[x_0, ..., x_n]$ Output: A list of integers \$[d_0,...
• 38

Only top scored, non community-wiki answers of a minimum length are eligible