I understand why Alexander Stepanov thought the complexity requirements were a good idea, but I am not convinced that in practice this delivers value. Worse, I don't see much sign C++ programmers care.

You mentioned particularly the C++ unstable sort std::sort. Famously although C++ 11 finally guarantees O(n log n) worst case complexity the libc++ stdlib didn't conform. They'd shipped worst case O(n squared) instead.

The bug report saying essentially "Hey, your sort is defective", was opened in 2014. By Orson Peters. It took until 2021 to fix it.