Алгоритм для nth_element

Недавно я узнал, что существует метод, называемый nth_element в STL. Процитировать описание:

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

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

Ответы