Недавно я обнаружил, что в STL существует метод с именем nth_element. Цитирую описание:
Nth_element похож на partial_sort в том, что он частично упорядочивает диапазон элементов: он упорядочивает диапазон [first, last) так, что элемент, на который указывает итератор nth, совпадает с элементом, который был бы в этой позиции, если бы весь диапазон [первый, последний) был отсортирован. Кроме того, ни один из элементов в диапазоне [n-й, последний) не меньше любого из элементов в диапазоне [первый, n-й).
Он утверждает, что в среднем имеет сложность O (n). Как работает алгоритм? Я не мог найти никакого объяснения этому.
