It is true that it won't tell you, for sure. It's just that UB means something very specific when discussing language semantics.
UB is really about the observable behavior of the abstract machine which is limited to the reads/writes to volatile data and I/O library calls [1]
[1] http://open-std.org/jtc1/sc22/open/n2356/intro.html
Edit: to clarify the example
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.