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 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Ā 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:

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.

Leave a Reply

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