[Bug libstdc++/81905] New: partial_sort slower than sort

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81905

            Bug ID: 81905
           Summary: partial_sort slower than sort
           Product: gcc
           Version: 8.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

(from https://stackoverflow.com/q/45455345/1918193 )

std::partial_sort of half an array can be slower than std::sort of the whole
array, because it uses heap sort vs introsort. There may be a size threshold
above which we could use a different algorithm than heap_select+sort_heap (say
a variant of introsort where after partitioning (possibly with a biased pivot),
depending where the pivot ends up, either we partial_sort the left and ignore
the right, or we sort the left and partial_sort the right), or some other
compromise.