Рассмотрим основные этапы параллельного алгоритма сортировки слиянием.

1. Нулевой процесс рассылает массив по блокам на остальные процессы. Блоки принимаются и сортируются слиянием (последовательный алгоритм слияния реализован в функции MergeSort ).

    t1=MPI_Wtime(); //начало отсчета времени

    MPI_Bcast(&size, 1, MPI_INT, 0, MPI_COMM_WORLD);

    int sizeBlock=size/n; //определяем размер блоков

    int ost = size%n;

    pmas = new int[sizeBlock];

    MPI_Scatter(&mas[rank*sizeBlock], sizeBlock, MPI_INT, pmas, sizeBlock, MPI_INT, 0, MPI_COMM_WORLD); //рассылка блоков

    MergeSort(pmas,0,sizeBlock-1);     //сортировка блоков

2. Процессы отправляют отсортированные блоки нулевому, он принимает их и последовательно сливает с помощью функции MergeMas.

if (rank==0) {

for (i=0; i<sizeBlock;i++) mas[i]=pmas[i];

for (i=1; i<n; i++){

            MPI_Recv (&mas[i*sizeBlock], sizeBlock, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &Status);

            MergeMas(mas, 0, (i+1)*sizeBlock-1, i*sizeBlock-1);

}}

    else MPI_Send (pmas, sizeBlock, MPI_INT, 0 , 0 , MPI_COMM_WORLD);

    t2=MPI_Wtime();