Сравните QuickSort и MergeSort: сложность и когда что выбрать.

QuickSort делит массив вокруг опорного элемента и в среднем даёт O(n log n) с малыми константами почти in-place, а MergeSort гарантированно работает за O(n log n) и стабилен, но требует O(n) дополнительной памяти.

QuickSort

• Partition вокруг pivot, затем рекурсия по обеим частям.
• Средний случай O(n log n); худший O(n²) — на отсортированном массиве при неудачном pivot. Лечится случайным выбором или median-of-three.
• Не стабилен, зато потребляет лишь O(log n) стека.

MergeSort

• Делит пополам и сливает отсортированные половины.
• Всегда O(n log n), стабилен, предсказуем на связных списках и во внешней сортировке, когда данные не влезают в память.
• Цена — буфер O(n).

Что выбирают на практике

Стандартные библиотеки используют гибриды: introsort (quick + heap при глубокой рекурсии) и Timsort (merge + вставки на естественных сериях).

Коротко для собеседования

QuickSort обычно быстрее на практике благодаря локальности данных и малым константам, но без случайного pivot может деградировать до O(n²). MergeSort выбирают, когда нужны стабильность, гарантированный худший случай или сортировка списков и данных на диске.