Skip to main content
11 votes

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 ...
Emil Jeřábek's user avatar
7 votes

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 ...
Display name's user avatar
3 votes

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-...
Tassle's user avatar
  • 881
2 votes

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 ...
gnasher729's user avatar
2 votes
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 ...
J..y B..y's user avatar
  • 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,...
Jarus's user avatar
  • 38

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