Skip to main content

New answers tagged

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

Top 50 recent answers are included