I believe that the C++ standard for std::sort does not guarantee O(n) performance on a list that's already sorted. But still, I'm wondering whether to your knowledge any implementations of the STL (GCC, MSVC, etc) make the std::is_sorted check before executing the sort algorithm?
Asked another way, what performance can one expect (without guarantees, of course) from running std::sort on a sorted container?
Side note: I posted some benchmarks for GCC 4.5 with C++0x enabled on my blog. Here's the results:
