Какая сложность алгоритмов сортировки

Что проверяют

Знаете ли вы оценки по времени и памяти и понимаете ли, что такое устойчивость.

Как отвечать

Сортировки сравнением не могут быть быстрее O(n log n) в худшем случае, это доказанная нижняя граница.

• пузырьком, вставками, выбором: O(n²). Вставками полезна на почти отсортированных данных, где даёт близко к O(n), и потому используется как добивка внутри быстрых алгоритмов;
• быстрая (quicksort): в среднем O(n log n), в худшем O(n²) при неудачном выборе опорного элемента. Памяти O(log n) на стек рекурсии. Неустойчива, но быстра на практике за счёт локальности;
• слиянием (merge sort): O(n log n) всегда, память O(n). Устойчива;
• пирамидальная (heapsort): O(n log n) всегда, память O(1). Неустойчива;
• timsort: гибрид слияния и вставок, O(n log n), устойчива, отлично работает на частично упорядоченных данных. Стандарт в Python и в Java для объектов;
• не сравнением: подсчётом и поразрядная дают O(n + k) и O(nk), но требуют ограниченного диапазона ключей.

Устойчивость это сохранение относительного порядка равных элементов. Важно, когда сортируют по нескольким полям последовательно.

Про Java стоит добавить конкретику: Arrays.sort для примитивов использует двухопорную быструю сортировку (неустойчивую, но памяти почти не требует), а для объектов timsort, потому что для объектов устойчивость важна.

Где спотыкаются

Называют только среднюю сложность, забывая худший случай quicksort.

Не учитывают память: merge sort требует O(n).

Не знают, что такое устойчивость и зачем она нужна.

Считают, что O(n log n) это предел для любых сортировок, забывая про подсчёт.