Let $S_n$ be the set of all possible permutations of $\{1,2,$dots,$n\}.$ The size of $S_n$ is given by $|S_n|=$

$nn*(n-1)cdots1.$ Each element of $S_n$ can serve as an input for a sorting algorithm.

We say that a sorting algorithm is $-$correct if the algorithm outputs a correctly sorted array

on at least $$ fraction of $S_n.$ For example, Quicksort corresponds to $=1$ since it is correct on

every possible input. If some algorithm is $\frac{1}{2}-$correct, then it will be correct on at least $\frac{n!}{2}$ many

inputs. In this question, we are interested in whether allowing $<mn\; id="EditorElement\_7119932">1</mn>$ can reduce the number of

comparisons needed.

Let $=\frac{1}{2}.$ Show that any $\frac{1}{2}-$correct comparison$-$based sorting algorithm must use

$)$ comparisons. $($This shows that even the easier task of correctly sorting $\frac{1}{2}$ of

the $n!$ possible inputs cannot be done faster than $O(nlogn).$