Все мы знаем про быструю сортировку, слиянием и прочие классические алгоритмы. Они отлично работают для большинства задач. Но вот задумался я: а насколько реально написать алгоритм, который будет сортировать миллионы элементов, допустим, чисел, за сотые доли секунды? С учетом современных многоядерных процессоров, конечно.
Я склоняюсь к тому, что это возможно, если использовать параллелизм и какие-то специфичные структуры данных, оптимизированные под конкретный тип данных. Например, если числа в определенном диапазоне, то можно попробовать какую-нибудь радиксную сортировку с хитрыми твиками. Или же какие-нибудь гибридные подходы, где на разных этапах применяются разные алгоритмы
Но реальна ли такая скорость в обычных условиях, без суперкомпьютеров и специфических данных? Или это скорее удел соревнований по спортивному программированию?
А вы как думаете? Сталкивались с задачами, где такая скорость была критична, и получилось ее добиться?