Сортировки — алгоритмы упорядочивания элементов по ключу.

Базовые

• Пузырёк/вставки/выбор — O(n^2), просты, для малых n.

• Merge sort — O(n log n), стабильный, требует память O(n).

• Quick sort — O(n log n) среднее, in-place, худшее O(n^2) без хорошего pivot.

• Heap sort — O(n log n), in-place, не стабильный.

Выбор

• Стабильность важна для многопольных ключей.

• In-place важен при ограниченной памяти.

• Для почти отсортированных — сортировка вставками/TimSort (Python, Java).

Примеры применения:

• Логи с многоуровневой сортировкой (дата, затем пользователь) — нужна стабильность → Merge/TimSort.

• Потоковые данные ограниченной длины — heap sort для получения топ-k (через min-heap).

• Списки уже почти отсортированы — вставками/TimSort дадут выигрыш.