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.
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|1 year ago
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|1 year ago
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.