If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]
Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is:


  Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has exactly $\ell$ elements smaller than it (i.e., it is the $(\ell+1)$st element).


Why is this enough? (The following is somewhat informal. See below for a more formal proof.) Suppose that your comparison algorithm outputs an element $x$ but knows only $j &lt; i-1$ elements smaller than it, that is, in the corresponding partial order, only $j$ elements are smaller than $x$. Then there is some total order in which element $x$ is in position $j+1 &lt; i$, and in particular, you cannot be sure that $x$ is the $i$th element. Similarly, if the algorithm knows only $j &lt; n-i$ elements larger than $x$, then there is some total order in which $x$ is in position $n-j &gt; i$ (using the dual version of the observation). Therefore the only way in which a comparison algorithm can be sure that $x$ is the $i$th element is if in the corresponding partial order, $x$ has exactly $i-1$ elements smaller than it and $n-i$ elements larger than it.

It remains to prove the observation. Given a partial order, we can generate a total order extending it by repeatedly performing the following operation:


  Choose a source (a minimal element) $y$, output it, and remove it from the partial order.


This (non-deterministic) algorithm outputs the elements in a certain order which is a total order extending the given partial order.

In order to apply this algorithm to prove the observation, consider the set of elements $P = \{ y : y \leq x \}$ which are at most $x$. In the first $\ell+1$ steps, we always choose a source from $P$ (this is always possible, though this requires an inductive argument). Then it continues in some arbitrary fashion. The resulting total order has $x$ as the $(\ell+1)$st element.



Our argument above, showing how the key observation implies the result, was somewhat informal. Here is a more formal treatment. We will actually show a slightly weaker result, that if a comparison algorithm finds the $i$th element correctly on all inputs with distinct elements, then it "knows" which elements are smaller than the $i$th element (can output them without further comparisons). The stronger result is left as an exercise to the reader.

We can think of the algorithm, when restricted to inputs with distinct elements, as a binary tree: each non-leaf compares two elements and has two children corresponding to the result of the comparison, and each leaf contains the output of the algorithm. We can furthermore assume that each vertex is reachable (we can always prune the tree to ensure this).

We can annotate each vertex with the partial order on the input elements, representing the algorithm's knowledge given the results of the preceding comparisons. We will show that at each leaf with output $x$, the corresponding partial order has exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

The proof is by contradiction. Suppose that there is some leaf with output $x$ at which there are $j &lt; i$ elements smaller than $x$ (the other case, of having less than $n-i$ elements larger than $x$, is handled symmetrically). The key observation shows that there is some linear order $L$ extending the partial order in which $x$ is not the $i$th element. If we had input this linear order to the algorithm, it would have reached the same leaf, and so would have answered incorrectly – contradicting our assumption that the algorithm is valid.

We conclude that at each leaf with output $x$ there are exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.