Finding the half with greatest elements in a set
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.