# Lower bound on comparison-based sorting

I have a question from one of the exercises in CLRS.

Show that there is no comparison sort whose running time is linear for at least half of the $$n!$$ inputs of length $$n$$. What about a fraction of $$1/n$$ of the inputs of length $$n$$? What about a fraction $$1/2^n$$?

I have arrived at the step where for a linear time sorter, there will we $$2^n$$ nodes in the decision tree, which is smaller than the $$n!$$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $$n!$$ inputs of length $$n$$". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $$n$$ will have $$n!$$ possible permutations.