It's STL-implementation specific. look in your c++ kit.
in mine (osx 10.6.7, g++ 4.2.1), it's in
/usr/include/c++/4.2.1/bits/stl_algo.h
and it uses an algorithm very similar to the original article
in mine (osx 10.6.7, g++ 4.2.1), it's in
/usr/include/c++/4.2.1/bits/stl_algo.h
and it uses an algorithm very similar to the original article
template<typename _RandomAccessIterator>
inline void
nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __nth);
__glibcxx_requires_valid_range(__nth, __last);
if (__first == __last || __nth == __last)
return;
std::__introselect(__first, __nth, __last,
std::__lg(__last - __first) * 2);
}If you look there, you will see it internally uses a heap.