Из приведенного в предыдущем разделе описания схемы работы сортировки слиянием видно, что выполнение алгоритмов сортировки каждой из частей исходного массива происходит независимо друг от друга. Этот факт является основополагающим для написания параллельной версии данной сортировки, с целью уменьшения времени работы алгоритма. Таким образом каждый из n процессов будет работать по приведенной ниже схеме.

Алгоритм действий процесса

1.      Определить и отсортировать блок массива, соответствующий данному процессу.

2.      Если номер процесса больше 0, то получить от предыдущего по номеру процесса часть массива (которая уже отсортирована) и отсортировать её совместно со своей методом слияния.

3.      Если номер процесса меньше n – 1, то послать следующему по номеру процессу свою отсортированную часть массива; иначе послать отсортированный массив процессу с номером 0.

4.      Если номер процесса равен 0, то получить от процесса с номером n – 1 отсортированный массив.

Таким образом, в данной работе следующие функции сортировки массива выполняются параллельно:

template <class T>
void merge(T *m1, T* m2, int l1, int l2, T* ret){
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2){
if (*m1 < *m2){
ret[n] = *m1;
m1++; l1--;}
else {
ret[n] = *m2;
m2++; l2--;}
n++;}
// Если закончился первый массив
if (l1 == 0){
for (int i=0; i<l2; i++){
ret[n++] = *m2++;}}
// Если закончился второй массив
else {
for (int i=0; i<l1; i++){
ret[n++] = *m1++;}}
}

// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
int n=1, l, ost;
T * mas1;
while (n<len)
{
 l=0;
 while (l<len)
 {
  if (l+n >= len) break;
  ost = (l+n*2>len) ? (len-(l+n)) : n;
  mas1 = new int[ost + n];
  merge(mas+l, mas+l+n, n, ost, mas1);
  for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
  delete [] mas1;
  l+=n*2;
 }
 n*=2;
}
}