[tialaramex]

Which of course makes it ironic that it says "We ought to be able to sort pretty fast, by now, using a Standard Library sort."

The C++ standard promised (since 1998) that the provided sorts are O(n log n).

But in fact popular C++ implementations ignored this and shipped quicksort - after all it's "pretty fast" but unfortunately this means if bad guys can choose your input (or you get unlucky) you get O(n squared)

Gradually they fixed this, libc++ updated to Introsort (last century's best attempt to do this) in 2021. In response to a ticket opened by Orson Peters.

These days you're also starting to see a trend towards the Rust-style "fast sort which implements a wide contract" design even in C++ implementations. Rust's sort doesn't actually promise this wide contract arrangement, but it does promise safety and the wide contract turns out to be the simplest way to do that.

What I mean there by "wide contract" is that these sorts don't blow up if your ordering rule is nonsense. They can't "sort" successfully because your ordering rule is nonsense, if A > B && B > A then too bad, we can't sort A and B. But they can and do gracefully give up, while many older C++ stdlibs just cause uncontrolled mayhem in this case.

[gpderetta]

I'm pretty sure that introsort was already implemented in the original STL last century.

In fact the standard didn't require O(log n) untill C++11 as all implementations were already using introsort, so allowing the previous more permissive O(n^2) bound was no longer necessary.

[tialaramex]

I don't know which is the "original STL" in this context. Alexander Stepanov's proposal of a standard template library for C++ pre-dates Musser's invention of introspective sorting (introsort). Stepanov is a smart guy but he's also somewhat famous so I'd guess if he invented it first we'd know that.

As I said, Orson filed a bug in LLVM bugzilla for libc++ going quadratic for adversarial input in 2014, and it was eventually fixed (by using introsort) in 2021.

There's a fun sideshow in that ticket, remember Orson actually wrote what is probably the best general purpose unstable sort at the time - but all he's done is open a ticket saying libc++ doesn't meet the minimum requirements. After a while, with the team having dragged their feet and still not even landed the patch to just use introsort somebody pipes up to report that they have benchmarked sorts and actually libc++ is faster than other popular C++ sorts (in their benchmark). So, Orson politely asks them to try PDQsort. That's the first time he explicitly mentions his Pattern Defecting Quicksort in the ticket, and maybe a harried LLVM bug handler wouldn't notice who filed the bug until then. Just another name.

But it's OK, the LLVM devs are unperturbed and ignore him, focusing instead on the minutiae of the performance numbers for their known defective unstable sort. Year later somebody eventually adds introsort to libc++ and closes the defect ticket. Nobody answers Orson's question, the answer of course is "Oh, yours is much faster".

[gpderetta]

Musser and Stepanov were working together on the STL. I think they were both at SGI at that time, and introsort was integrated into the SGI STL (around the same time the STL was standardized, I guess introsort was too new to require it in C++98); from there introsort made it into most other standard library implementations which are directly derived from SGI STL.

libc++ is notable for being one of the few from-scratch implementations.