Finding the half with greatest elements in a set Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this in $O(n)$ time?
Proceed in two phases.


Determine the median of the input.
Partition the input with the median as the pivot (cf. Quicksort).


Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.