> Where do you see three sorts
stable_sort, sort, and sort_heap
The creator Alex Stepanov also included insertion_sort (used in sort) but it was rejected by standard committee.
That suggests that the idea that complexity is primarily to compare is wrong, because then why would anyone pick insertion_sort? Of course there are real world cases where it is the right choice. But if you need the complexity guarantee, then it's not.
> shiny new general purpose sort
I don't want it in the standard until it's proven useful and has some longevity, not just a micro benchmark. Shiny and new are exactly the wrong adjectives.
Why can't you include a header?
> quicksort
Introsort is simply a variant of quick sort with heap sort as a fallback to avoid the worst case, and insertion sort at the lowest level.
Anyone who tried to pass off naiive quick sort simply wasn't educated about the topic, so it's good that they were not standard compliant.