Skip to main content
13 votes
Accepted

Find odd-ranked numbers from a list

Lemma 1. Any comparison-based algorithm requires $\Omega(n\log n)$ comparisons in the worst case. Proof sketch. Let $A$ be any comparison-based algorithm for the problem. Let $x=(x_1, x_2, \ldots, ...
Neal Young's user avatar
  • 10.8k
12 votes
Accepted

Expected number of random comparisons needed to sort a list

This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes ...
Neal Young's user avatar
  • 10.8k
12 votes
Accepted

Number of permutations that satisfy a given set of comparisons

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has. This ...
a3nm's user avatar
  • 9,547
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
9 votes

Expected number of random comparisons needed to sort a list

I believe this takes $\Theta(n^2)$ oracle calls without replacement, and $\Theta(n^2\log n)$ oracle calls with replacement. Lower bound: Assume my list has a single pair $x[i], x[i+1]$ out of order. ...
SamM's user avatar
  • 1,685
9 votes
Accepted

Original reference for Huffman shaped Merge Sort?

I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested. Knuth mentions runs in his description of "natural merge sort" (page 160 of the ...
J..y B..y's user avatar
  • 2,776
9 votes
Accepted

Computing topological sort while keeping edges "short"

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH. It is NP-complete: M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth: "Complexity Results for Bandwidth Minimization" SIAM ...
Gamow's user avatar
  • 5,772
9 votes
Accepted

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Update: I expanded this answer into a paper Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons. Yes, such an algorithm exists. I will only prove the $\mathrm{lg}(n!)+o(n)$ bound, but ...
Dmytro Taranovsky's user avatar
8 votes

"Almost sorting" integers in linear time

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.: https://www.inf.ethz.ch/personal/smilos/asort3.pdf Unfortunately, the running time is not quite linear. The article ...
Trixie Wolf's user avatar
8 votes
Accepted

Quick-select contiguous subarray

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
Chao Xu's user avatar
  • 4,479
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
6 votes
Accepted

Most efficient inplace merge algorithms (stable and unstable)

TLDR The latest stable one with linear moves is from 2008 and with detailed description can be found here. According to their benchmarks, it is less than two times slower than standard merge that ...
Guest's user avatar
  • 76
6 votes
Accepted

Sorting a programs instructions until it works

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$. (Of course, that does not guarantee that you found the correct ...
Bjørn Kjos-Hanssen's user avatar
6 votes

Expected number of random comparisons needed to sort a list

Not a complete answer, but here's a start. Consider the index $p_{k} \in \{1,\dots n \}$ to represent the $k$th object in the series, with respect to order. We have: $$x[p_{k}] < x[p_{j}] \...
user3257842's user avatar
6 votes
Accepted

Is sorting pairwise distances as hard as sorting arbitrary points?

This is an open question even for one-dimensional point sets. In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.
Jeffε's user avatar
  • 23.2k
5 votes

Under what models do we know linear time sorting?

One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model. Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and ...
Shaull's user avatar
  • 5,656
5 votes
Accepted

how to achieve a topological sort of an given sequence with minimum swaps

This problem is NP-complete. I will prove NP-hardness below Source Problem Colored Token Swapping on Cliques: In the colored token swapping problem, we are given a graph with a colored token ...
Mikhail Rudoy's user avatar
5 votes

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

Based on Sasho Nikolov's very helpful comment, it seems that both papers use similar models of complexity which lead to unreasonable conclusions, such as the implication that any problem in PSPACE or #...
kodlu's user avatar
  • 2,070
4 votes

Quick-select contiguous subarray

When $k = \lceil (s-t)/2 \rceil$, this the range medians problem. There are solutions which are much better than the two trivial ones: you can answer the first $q$ queries in time $O(n\log q + q\log ...
Sasho Nikolov's user avatar
3 votes

Sorting a programs instructions until it works

Others have pointed out this is semidecidable. In most programming languages, the problem is NP-hard. In particular, the following problem is NP-hard: Input: a set of lines of code Question: does ...
D.W.'s user avatar
  • 12.2k
3 votes

Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?

Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network ...
xavierm02's user avatar
  • 556
3 votes
Accepted

Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I got a reply from the problem author, wanted to post the info here for reference: Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in ...
Elliot Gorokhovsky's user avatar
3 votes

Lower bound for sorting without using a decision tree model

If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of ...
Joshua Grochow'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

Patience Sort+ ping pong merge implementation

I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays: A typical merge operations takes two runs in an array and merges them in another arra; then, it ...
Morwenn's user avatar
  • 121
2 votes

finding smallest k elements in array in O(k)

First use $O(n)$ to build a min-heap. It is known that we can use $O(k)$ to find the $k$ smallest elements in a min-heap: Frederickson, Greg N., An optimal algorithm for selection in a min-heap, Inf....
hqztrue's user avatar
  • 112
2 votes
Accepted

"Almost sorting" integers in linear time

As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant ...
a3nm's user avatar
  • 9,547
2 votes
Accepted

A sorting algorithm that uses the minimum comparasions possible

Using simple methods, it can be shown that any comparison-based algorithm must perform at least $n\log{n}-o(nlogn)$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort ...
user3209423940248's user avatar
2 votes
Accepted

Formally prove that the loops of this sorting algorithm will terminate

Since the loop variables $i$ and $j$ are not modified in the loop body, you can compute the exact number of iterations. The inner loop is executed $n-i$ times in each iteration of the outer loop, so ...
Mark Dettinger's user avatar
2 votes

Lower bound for sorting without using a decision tree model

The paper "Sorting and Element Distinctness on One-Way Turing Machines" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.
Jan Johannsen's user avatar

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