Вот реально интересно, почему быстрая сортировка (QuickSort) так часто используется в библиотеках и учебниках, когда у нее есть такой уязвимый худший случай O(n^2)? Казалось бы, алгоритмы вроде MergeSort или HeapSort имеют гарантированную O(n log n) производительность, что намного надежнее. Неужели средняя производительность настолько хороша, что перевешивает все риски?
Или есть какие-то хитрые модификации QuickSort, которые нивелируют эту проблему? Кмк, понимание причин популярности этого алгоритма — ключ к более глубокому пониманию анализа алгоритмов в целом. Что думаете?