алгоритм для [закрытого] nth_element

Я недавно узнал, что там существует метод, названный nth_element в STL. Заключить описание в кавычки:

Nth_element подобен partial_sort, в котором он частично заказывает диапазон элементов: это располагает диапазон [сначала, в последний раз), таким образом, что элемент, на который указывает энный итератор, совпадает с элементом, который был бы в том положении, если весь диапазон [сначала, в последний раз), был отсортирован. Кроме того, ни один из элементов в диапазоне [энный, в последний раз), меньше, чем любой из элементов в диапазоне [первый, энный).

Это утверждает, что имело O (n) сложность в среднем. Как алгоритм работает? Я не мог найти объяснение его.