Знаете ли вы, что алгоритм быстрой сортировки (QuickSort) был изобретен Чарльзом Хоаром в 1960 году, когда он работал над сортировкой русских слов для машинного перевода?
Интересный поворот: изначально алгоритм назывался “Partition Exchange Sort”, но редактор научного журнала посчитал это название слишком длинным и предложил более лаконичное “QuickSort”!
А вот математическая изюминка: средняя сложность QuickSort составляет $ O(n \log n) $, что делает его одним из самых эффективных алгоритмов сортировки. При этом в худшем случае (когда массив уже отсортирован) сложность падает до $ O(n^2) $, но это легко исправить случайной перестановкой элементов перед сортировкой!
Кстати, сам Хоар признавался, что потратил две недели на поиск ошибки в своем алгоритме, потому что не учел случай с повторяющимися элементами в массиве 😅