Personally the implementation of nth_element is a much more interesting thing to see than just knowing it exists.
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
If you look there, you will see it internally uses a heap.
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);
}