Три теоремы о сортировках

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort.

Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

https://habr.com/ru/hubs/cpp/articles/

#cpp #programming

👉 @cpp_lib