Как устроен std::sort
Вопрос
Расскажите, как устроен std::sort, чем он отличается от stable_sort, partial_sort и nth_element и как выбирать.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Introsort: quicksort + heapsort при глубокой рекурсии + вставки на малых кусках
O(n log n) в худшем, нестабилен, на месте
stable_sort: слияние, стабилен, нужна память
partial_sort для top-k O(n log k), nth_element O(n) в среднем для k-й статистики
Строгий слабый порядок компаратора
Random access итераторы
Что могут спросить следом
- Почему quicksort в чистом виде не используют?
- Как отсортировать по двум полям?
Разбор
std::sort в основных реализациях это introsort. Он начинает как быстрая сортировка с медианой из трёх, следит за глубиной рекурсии и, если она превышает примерно 2·log n, переключается на пирамидальную сортировку: так худший случай остаётся O(n log n). Маленькие отрезки, около 16 элементов, досортировываются вставками, это быстрее на кеше. Сортировка нестабильная и работает на месте, требует итераторы произвольного доступа и компаратор со строгим слабым порядком, иначе UB. Если нужен порядок равных, беру stable_sort, это слияние с дополнительным буфером. Если нужны только первые k элементов по порядку, partial_sort, O(n log k). Если нужна медиана или порог k-й статистики без порядка, nth_element, в среднем O(n). Сортировку по нескольким полям делаю одним sort с компаратором через std::tie или проекцией в ranges.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.