Сортирущие сети, они сегодня актуальны?

На GPU и подобных устройствах bitonic sort и odd-even merge sort вполне себе используются.

В какого рода задачах?

В какого рода задачах?

Ранговая фильтрация сигналов и изображений (например) на основе формирования вариационного ряда: аппаратные сети сортировки в реальном времени (РВ).

Робастный анализ данных РВ по вариационному ряду: медиана, порядковые статистики, интерквантильный размах, ...

Применение: от РЛС до бытовых видеокамер.©

Хорошие примеры, спасибо!

Актуальны при реализации в железе (FPGA, ASIC), а так же на GPU.

Просто сегодня сдул пыляку с монографии Седжвика и, оппа, «Методы сортировки специального назначения», думаю, а вдруг оно уже не актуально. Ну и как у классика:

Пошел, сел у берега моря;

Там он стал веревку крутить,

Да конец ее в море мочить.

В общем, вы поняли :-)

На самом деле, в очень широком диапазоне задач. Про статистику и связанные задачи уже выше написали. Но это не всё: часто на GPU сортировка нужна для того, чтобы обойтись минимумом условных переходов (они тормознутые весьма), например, если нужно подсчитать гистограмму, что не сводится к одной лишь статистике (пример: метод PIC).

Часто сортирующая сеть позволяет строить эффективные алгоритмы для многих задач (не для задач сортировки). Порядок, в котором включены сортирующие элементы сети, указывает на последовательность действий совсем других алгоритмов.

Подробнее тут:

http://dl.acm.org/citation.cfm?id=322410&CFID=635804519&CFTOKEN=78300842

Я могу даже привести пример задачи, для которой есть теоретическая оценка сложности O(n log n), но на практике такой алгоритм неприменим, так как базируется на сортирующей сети AKS (у неё глубина O(log n), но огромная константа). При этом этот же подход для сети Бетчера дает сложность O(n log^2 n). То есть если бы нашли хорошую сортирующую сеть глубиной O(log n), то сразу бы получили и здесь практически значимый результат.

Спасибо за ответ.

так как базируется на сортирующей сети AKS (у неё глубина O(log n),но огромная константа).

Уже читал в английской Википедии об этом.