Alex Rivera | Logout

Does std::sort check if a vector is already sorted?

Asked 2011-07-04T04:36:19.300
45

I believe that the C++ standard for std::sort does not guarantee O(n) performance on a list that's already sorted. But still, I'm wondering whether to your knowledge any implementations of the STL (GCC, MSVC, etc) make the std::is_sorted check before executing the sort algorithm?

Asked another way, what performance can one expect (without guarantees, of course) from running std::sort on a sorted container?

Side note: I posted some benchmarks for GCC 4.5 with C++0x enabled on my blog. Here's the results:

Comparison of std::sort and std::is_sorted

c++ sorting gcc c++11 stl
Edit
Report

1 Answer

1

And why would any implementation do that check? What would it gain? -- Nothing in average. A good design rule is not to clutter implementation with optimizations for corner cases which make no difference in average. This example is similar to check for self-assignment. A simple answer: don't do it.

answered 2011-07-04T06:50:26.640

Your Answer