лучше, чем сортировка слиянием (сложность времени)?

Question

Пожалуйста, объясните, почему в алгоритме C ++ sort () используется introsort? и в каких случаях он работает лучше, чем обычный алгоритм mergeSort

Answer 1

В большинстве случаев быстрая сортировка предпочтительнее сортировки слиянием. Но быстрая сортировка плохо работает с данными, которые почти отсортированы с самого начала; интросорт исправляет некоторые извращенные случаи.

Answer 2

лучше, чем сортировка слиянием (сложность времени)?

Оба алгоритма имеют одинаковую асимптотическую сложность по времени: O (N log N) как в наихудшем, так и в среднем случае.

Пожалуйста, объясните, почему в алгоритме C ++ sort () используется introsort?

Предполагая, что вы имеете в виду стандартный алгоритм std::sort, он не обязательно будет реализован с использованием интросорта. Возможно, вы имеете в виду некоторые конкретные реализации.

и в каких случаях он работает лучше, чем обычный алгоритм mergeSort

Обычно в случаях, когда данные имеют высокую локальность кэша и длина входного диапазона мала.