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.

Shortlink:

Comments

comments

This entry was posted in Programming and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>