Here's something more complicated, which performs $n + o(n)$ comparisons, and achieves an approximately correct list with high probability.
Suppose you want to partition a set $V$ of $n$ elements into a disjoint union $L \cup S$ of a set of larger elements and a set of smaller elements, where every $s \in S$ is bounded above by every $\ell \in L$, and where where $# L \approx \sigma n$ for some constant $0 < \sigma < 1$. Then with only a constant (or smaller than constant) probability of failure, we can select $L$ in such a way that it contains all of the $\sigma n$ largest elements of $V$, together with only a constant (or decreasing) fraction of extraneous elements.
Algorithm
1. Obtain a sample $X$ of $N$ randomly selected elements, for some $0 < N < n$ which we will specify later. Sort them. This takes time $O(N \log(N))$.
2. For some parameter $\delta > 0$, find a pivot $x^\ast$, chosen to be the $(\sigma + \delta/2) N^{\text{th}}$ largest element of $X$. (If there are multiple elements with the same value, put all of the copies of the value of $x^\ast$ which precedes the $(\sigma + \delta) N^{\text{th}}$ largest element into $L$; put the rest of the values, including $x^\ast$ itself, into $S$.)
3. Compare all of the remaining elements of $V \smallsetminus X$ to $x^\ast$. 743
If they are larger, put them in $L$; otherwise, put them in $S$.
Let $M$ be the set of the $\sigma n$ largest elements of $V$. We will consider the probability that $L$ contains all of the elements of $V$, but no more than $\delta n$ additional elements of $V$ beyond that.
Probabilistic and run-time analysis.
The probability that any particular element of $X$ is in $M$ is, by definition, $\sigma$. In particular, by the <PERSON> bound, the probability that $X$ contains as many as $(\sigma + \delta/2)N$ elements of $M$ scales as $$ \Pr\biggl[ #(X \cap M) \geqslant (\sigma + \delta)N \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr),$$ and that therefore $$ \Pr\biggl[ x^\ast \in X \cap M \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr). $$ Because $L$ is constructed to be all of the values which are larger (or at least succeed) $x^\ast$ in $V$, it follows that $M$ is a subset of $L$ provided that $x^\ast \notin M$. Then, we have $$ \Pr\biggl[ M \not\subseteq L \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr), $$ for any $\delta > 0$. We want more than this, however: we would like the number of extraneous elements in $L$ not to be too large. The expected number of elements in $L$ is going to be $(\sigma + \delta/2)n$, but we're interested in the probability with which it is less than $(\sigma + \delta)n$, as well as being at least $\sigma n$. That is, we want to know the probability with which the number of elements is bounded by $\delta n/2$ from the expected value, which is $$ \Pr\biggl[ |# L - \sigma n | \geqslant \delta/2 \biggr] ~~\leqslant~~ 2 \exp\Bigl( -\delta^2 N/2\Bigr). $$ If we want this probability of failure to be at most some value $0 < p < 1$, we then require $$\begin{equation} p \geqslant 2\exp\Bigl( -\delta^2 N/2\Bigr) ~~\implies~~ N \geqslant \frac{2\ln(2/p)}{\delta^2}\;. 532