Какова наихудшая временная сложность сортировки массива строк с использованием функции sort () в c ++?

Question

Пример

string input[3]={"Earth","Mars","Mercury"};
sort(input,input+3);

Answer 1

До C ++ 11 сложность в среднем составляет N.log(N), а сложность наихудшего случая зависит от реализации вашей стандартной библиотеки. Для более поздних версий языка стандарт требует, чтобы сложность была точно N.log(N).

С https://en.cppreference.com/w/cpp/algorithm/sort:

Сложность

O (N · log (N)) , где N = std::distance(first, last) сравнения в среднем. (до C ++ 11) O (N · log (N)) , где N = std::distance(first, last) сравнения. (начиная с C ++ 11)