# Tag Info

Accepted

### Would an optimal sorting network ever have to swap two numbers the "wrong" way

How do you decide what the "wrong way" is? Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn'...
• 23.5k

### Sorting sequence with $O(n^{\frac{3}{2}})$ inversions

You can't sort it in linear time. Suppose you have $n$ items, and you divide them into $\sqrt{n}$ consecutive blocks of $\sqrt{n}$ items each. You need to take $\sqrt{n} \log \sqrt{n}$ comparisons ...
• 23.5k
Accepted

### Locally sorted sequences

Your problem is solved in the paper Spheres of Permutations under the Infinity Norm — Permutations with limited displacement by Torleiv Kløve. See also A002524 and other sequences linked there. ...
• 14.1k
Accepted

### Reducing sorting to max-flow

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow ...
• 50.2k
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 ...
• 2,391
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 ...
• 5,712

### "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 ...
• 181

### Sorting sequence with $O(n^{\frac{3}{2}})$ inversions

This is a topic of "adaptive sorting." As a starter, see the wikipedia page https://en.wikipedia.org/wiki/Adaptive_sort . It is known that we can sort a sequence of length $n$ with $k$ inversions ...
• 3,716
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.
• 4,256
Accepted

### Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

It seems not. Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further ...
• 1,553
Accepted

### Is the bitonic sort algorithm stable?

No, bitonic sort is not stable. For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ...
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 ...
• 2,237
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 ...
• 4,400
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$.
• 22.8k

### 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 #...
• 1,986

### Sorting using ring operations

This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible. I think you're ...
• 50.2k
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 ...
• 2,718

### 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 ...
• 5,261

### 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 ...
• 10.4k

### 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 ...
• 521
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 ...
Accepted

### How to Quantify Entropy in a Data Set

Inversions are one way to measure "disorder" in a list: Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$. However,...
• 171

### Determining what can be achieved by a permutation of elements of a noncommutative group

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open. proof Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$. Then ...
• 2,718