$($a$)$ Consider comparison$-$based sorting algorithms whose inputs are sequences

of $n$ distinct elements from some ordered set.

Prove or disprove the following statements:

i$.$ There exists a comparison$-$based sorting algorithm whose running time

is linear for at least a fraction of $\frac{1}{n}$ of all possible inputs of length $n.$

ii$.$ There exists a comparison$-$based sorting algorithm whose running time

is linear for at least a fraction of $\frac{1}{2^n}$ of all possible inputs of length $n.$