# Tag Info

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

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

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

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

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

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