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