title: Does std::sort check if a vector is already sorted?
body: <p>I believe that the C++ standard for <a href="http://en.cppreference.com/w/cpp/algorithm/sort" rel="noreferrer"><code>std::sort</code></a> 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 <a href="http://en.cppreference.com/w/cpp/algorithm/is_sorted" rel="noreferrer"><code>std::is_sorted</code></a> check before executing the sort algorithm?</p>
  
  <p>Asked another way, what performance can one expect (without guarantees, of course) from running <code>std::sort</code> on a sorted container?</p>
  
  <p>Side note: I posted <a href="http://lexfridman.com/blogs/research/2011/07/04/sorting-a-sorted-list-in-c/" rel="noreferrer">some benchmarks</a> for GCC 4.5 with C++0x enabled on my blog. Here's the results:</p>
  
  <p><img src="https://i.stack.imgur.com/7iYtZ.png" alt="Comparison of std::sort and std::is_sorted"></p>