https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103621
Bug ID: 103621
Summary: stable_sort could call std::__merge_sort_with_buffer
directly in typical case
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: riad93 at mail dot ru
Target Milestone: ---
So, currently __stable_sort is implemented this way:
if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
_DistanceType(__buf.size()), __comp);
which means that on the topmost iteration the merge the split will be done in a
naive way, and the copy+merge will happen even in typical case when there's
enough memory for everything.
Subjectively, it makes sense that in general calling
std::__merge_sort_with_buffer should be faster (otherwise why would it exist),
but I wasn't able to measure any difference yet.