ALL THREE PROBLEMS NEED USE O(n) comparisons

Let Sn be the set of all possible permutations of {1,2,,n}. The size of Sn is given by Sn=n ! = n(n1)1. Each element of Sn 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 Sn. For example, MergeSort corresponds to =1 since it is correct on every possible input. If some algorithm is 1/2-correct, then it will be correct on at least n!/2 many inputs. We are interested in whether allowing