It came to my attention that I didn’t know how well STL sorting algorithms performed on a vector of values that are already sorted. One would hope it would be close to $latex O(n)$. This page does a comparison of various algorithms on vectors that are sorted to varying degrees. However, I’m interested in the case when the vector is fully sorted. A simpleĀ $latex O(n)$ would remove the need to run the sorting algorithm on a list that’s already sorted. It makes perfect sense that the STL implementation of std::sort does not perform this check. I confirmed this fact by running the following simple test:

1 2 3 4 5 6 7 |
for(int s=0; s<=10; s++) { const int n = 1000 * 1000 * 10 * s; vector<int> v(n); iota(v.begin(), v.end(), 0); std::sort(v.begin(), v.end()); std::is_sorted(v.begin(), v.end()); } |

The results with no optimization turned on:

The results with -O2 optimization:

**Conclusion:** if you expect that the list might be sorted more often than not, run
std::is_sorted on it first.