@RGS Quickselect with median-of-medians pivot selection is O(n). There's a lot of more recent research on improving the constant factor as well.

Thanks for the reference @Marshall, I didn't know about quickselect