[Bug libstdc++/35968] New: nth_element fails to meet its complexity requirements

[sjhowe at dial dot pipex dot com]

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