The C++ standard library method std::nth_element states complexity; linear time on average. ( http://en.cppreference.com/w/cpp/algorithm/nth_element http://en.c

The C++ standard library method std::nth_element states complexity; linear time on average. ( http://en.cppreference.com/w/cpp/algorithm/nth_element http://en.cppreference.com/w/cpp/algorithm/nth_element ) I wonder if there are other possible implementations?