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.
