> Another idea in STL is to provide many algorithms, which is why there are 3 sorts.
Where do you see three sorts with different behaviour? I see two, an unstable sort just named "sort" and a stable sort.
sort performs O(N⋅log(N)) comparisons and so does the stable sort, although to be fair it also promises to work (more slowly, O(N⋅log*2(N)) instead) if there's no scratch space.
We don't get to ask for the no scratch variant, so we can't count that separately.
And these big-O values are totally uninteresting because they're typical for every modern sort, when people announce a shiny new general purpose sort it has the same complexity numbers. Does your STL have it? Who knows, the standard doesn't specify.
And that gets back to my earlier point, Introsort, the typical sort you'd find in an C++ program today, is relatively modern, and C++ was standardised in 1998. So actually quicksort was often in a "complying" C++ stdlib because hey, that's good right? Well, no, Quicksort's worst case has O(n*2) so it's actually forbidden by the STL's documentation, but nevertheless it was shipped because for many real world uses it's fast.
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.
I had never seen std::sort_heap before, that is kinda cool.
I'm torn about whether this constitutes a sort though. Like, yeah, in some sense this is the meat of a heap sort, but, it's the caller's job to provide the data as a heap first and of course this is C++ so if we screw that up it's Undefined Behaviour.
> I don't want it in the standard until it's proven useful and has some longevity
I wasn't advocating for such things to be in the standard but to be in the implementation. One of the worst sins of WG21 has been standardising implementations, as they did with std::unordered_map and continued to do in newer C++ versions.
And you're wrong, these people knew exactly what they were doing. You've probably used a stdlib which did this (such as libc++), the reason was very simple: Despite the big-O complexity, in practice quicksort was fast while heap sort, though compliant, is usually slower. Benchmarks matter. Big-O not so much.
Like I said, Introsort was new, and as you've explained you want to wait until things have "some longevity" before standardising them, so the stdlibs didn't take Introsort at first. LLVM took Introsort for libc++ in 2021, Microsoft landed a compliant sort some years earlier. Neither complied with C++ 98 initially.
I mean the big joke for LLVM is that the bug ticket about their sort complexity which sat in a pile unresolved until after Joe Biden became president was by Orson Peters. It's like realising the guy who pointed out that your physics textbook has the formula for mass-energy equivalence wrong is Albert Einstein. Gee, I wonder if Orson has any idea for how to fix this libc++ bug...
Where do you see three sorts with different behaviour? I see two, an unstable sort just named "sort" and a stable sort.
sort performs O(N⋅log(N)) comparisons and so does the stable sort, although to be fair it also promises to work (more slowly, O(N⋅log*2(N)) instead) if there's no scratch space.
We don't get to ask for the no scratch variant, so we can't count that separately.
And these big-O values are totally uninteresting because they're typical for every modern sort, when people announce a shiny new general purpose sort it has the same complexity numbers. Does your STL have it? Who knows, the standard doesn't specify.
And that gets back to my earlier point, Introsort, the typical sort you'd find in an C++ program today, is relatively modern, and C++ was standardised in 1998. So actually quicksort was often in a "complying" C++ stdlib because hey, that's good right? Well, no, Quicksort's worst case has O(n*2) so it's actually forbidden by the STL's documentation, but nevertheless it was shipped because for many real world uses it's fast.