[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.