Does std::sort check if a vector is already sorted?

Question

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:

Answer 1

Implementations are free to use any efficient sorting algorithm they want so this is highly implementation dependant

However I have seen a performance comparison of libstdc++ as used on linux and against libc++ the new C++ library developed by Apple/LLVM. Both these libraries are very efficient on sorted or reverse sorted data (much faster than on a random list) with the new library being considerable faster then the old and recognizing many more patterns.

To be certain you should consider doing your own benchmarks.

Answer 2

No. Also, it's not logical to have is_sorted() called for any STL implementation. Since, is_sorted() is available already as a stand-alone. And many users may not want to waste execution cycles unnecessarily to call that function when they already know that their container is not sorted.

STL also should be following the C++ philosophy: "pay per use".

Answer 3

Wow! Did you have optimizations all the way cranked up?

the results of your code on my platform (note the values on the vertical axis).