Sorting a Sorted List in C++

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:

    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.