Quickselect. This is how you select the n:th element in a list in average O(n) time.

It is basically quicksort but it only continues sorting the relevant subproblems. For instance, if you want to select the element n:th where n is less than length/2 you will never have to consider the second half after the first partitioning step, and so on.

Obviously, this still has quadratic worst case performance, just like quicksort.