# Tag Info

Accepted

• 18.2k

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

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

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

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

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

### 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....
• 112
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 ...
• 9,547
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 ...
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 ...