Представим возможный вариант параллельной программы обобщенной быстрой
сортировки.
Инициализируется исходный массив (например, при помощи генератора
случайных чисел), причём его длина должна быть кратна числу процессов для
облегчения реализации.
Имеющимся процессам рассылаются его части.
Процессы сортируют свой блок данных при помощи обычного последовательного
алгоритма быстрой сортировки.
В цикле от размерности гиперкуба до 1:
1. Определяются процессы, входящие в грань гиперкуба нужной
размерности, и сформировать из них группу;
2. Главный процесс в грани определяет ведущий элемент и рассылает его всем
процессам гиперкуба.
3. Каждый процесс разбивает имеющийся блок данных в соответствии с ведущим
элементом (в одном все элементы меньше, в другом больше). Блок может оказаться
пустым.
4. В каждой паре, образованной двумя процессами, находящимися на одном
ребре по текущему измерению, процесс с меньшим номером принимает от большего
тот блок данных, элементы в котором меньше ведущего, и сливает его со
своим; а ему пересылает свой блок данных, в котором элементы больше
ведущего.
Затем данные всех процессов собираются в один отсортированный
массив.
