# How often can a linear speed sort succeed?

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.

What kind of bounds can we place on the success rate of such an algorithm? It obviously can't succeed 100% of the time, since then it would just be an ordinary list sorting function and it would have to be $\Omega(n \log n)$. The answer isn't 0% success, since you can check if it sorted in $\mathcal O (n)$, and so you can sometimes succeed.

Of course, the success rate depends on how we are choosing the list. The uniform case would be best, but any kind of bounds would be helpful.

• $\Omega(n \lg n)$ lower bound is only comparison based sorting algorithms. A similar lower bound holds for the average case complexity of comparison based sorting algorithms. IIRC, there is a question about it on Computer Science explaining this. – Kaveh Apr 22 '16 at 4:26
• Hint: how many leaves can a comparison tree of linear height have, and what fraction of $n!$ is this? But this is not a research-level question, so it's off-topic here. – David Eppstein Apr 22 '16 at 17:48
• @DavidEppstein Oh sorry, I should have read the help center better. I'll ask for a migration. – PyRulez Apr 22 '16 at 18:27
• In what computational model? Comparison-based sorting methods only? (en.wikipedia.org/wiki/Comparison_sort) – D.W. Apr 23 '16 at 4:11
• One interesting extension of the lower bound is that comparison-based sorting should take $O(nH)$ time where $H$ is the entropy of the key distribution. As an exercise, what sorting algorithms take $O(n \log n)$ time in the general case, but $O(n)$ time when there are only two sort keys (e.g. sorting booleans)? – Pseudonym Apr 23 '16 at 6:35

David Eppstein gave away the answer: an $O(n)$ comparison-based algorithm will succeed on a negligible fraction of permutations. One way to see that is that an $O(n)$ algorithm can only take care of $2^{O(n)}$ different input permutations, compared to the $n! = 2^{\Omega(n\log n)}$ possible ones.