Question $2$

QUICKSORT requires manipulating an array so that one element can be used as a pivot. Interestingly,

some elements can be used as pivots without changing the array. Design an algorithm that, given an

array, returns a list of valid pivots in tilde$(O)(n)$ time and prove its correctness.

Note: tilde$(O)(n)$ is called soft$-O.$ A function $f(n)$ is tilde$(O)(g(n))$ if $f(n)inO(g(n)lo{g}^k(n))$ for some $k.$ That is$,$

$f(n)$ is $O(g(n))$ after ignoring $log$ factors.