Я считаю, что стандарт С++ для std::sort
не гарантирует производительность O (n) в уже отсортированном списке. Но тем не менее, мне интересно, насколько вам известно, какие реализации STL (GCC, MSVC и т.д.) Делают проверку std::is_sorted
перед выполнением алгоритм сортировки?
С другой стороны, какую производительность можно ожидать (без гарантий, конечно) от запуска std::sort
в сортированном контейнере?
Боковое примечание: я опубликовал некоторые ориентиры для GCC 4.5 с включенным С++ 0x в моем блоге. Здесь результаты: