Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can return anything, even a completely unsorted array.)
I know that using comparison model of sorting algorithms there is a lower bound of $\Omega(n \log n)$ so I try to make a proof by contradiction and to get to the fact that if such an algorithm exist then we can sort by comparison sort in linear time.
2 Answers 2
Suppose that a comparison-based sorting algorithm sorts the set of permutations $\Pi$ correctly. Construct the comparison decision tree underlying the algorithm, with permutations as leaves. Each permutation in $\Pi$ must appear as a leaf (why?), hence the tree must have depth at least $\log_2 |\Pi|$ (why?).
There are n! possible permutations of n items, which is why we need $\log_2(n)$ comparisons, rounded up to the next integer since we can't have half a comparison, to distinguish them. That number is quite close to $n \cdot \log_2(n / e)$. To sort half of the possible inputs, we need ONE fewer comparison. To get to linear time, we have to restrict the number of inputs a lot more.
On the other hand, we can sort an array for example in 100n comparisons when $\log_2(n / e) < 100$ or $n/e < 2^{100}$ or $n < e \cdot 2^{100}$. The largest computer that I can't afford to buy would sort any array that I could store in memory in 40n comparisons.