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