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: