# Sorting algorithm which sorts half the possible inputs in linear time

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.

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