nth_element in 4.3.0 fails to meet its complexity requirements. This is basically intraselect by Dave Musser. The question is "What algorithm should you switch to when quickselect fails?"
In the codebase __heapselect() is called. But this in O(N * log N). __heapselect() is O(middle-first) + O((last-middle) * log(last-first)) which is O(N * log N) and the C++ standard requires nth_element to be O(N). __heapselect() is no use at all here. Better still is median-of-medians of groups of 5 (and plenty of proofs that it is O(N)) or approximate median finding and that is still O(N) See www.cs.wpi.edu/~hofri/medsel.pdf In the best or average case, intraselect is O(N) partitioning + O(1) finding a suitable partition element In the worse case, intraselect is O(N) partitioning + O(N) finding a suitable partition element Stephen Howe -- Summary: nth_element fails to meet its complexity requirements Product: gcc Version: 4.3.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: sjhowe at dial dot pipex dot com http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968