Алгоритм делит исходный массив на P частей по количеству выделенных программе процессоров. Части сортируются параллельно и независимо друг от друга, каждая стандартным последовательным алгоритмом на своём процессоре. Затем (после того как все потоки, выполнявшие раздельную сортировку, завершатся) все части сливаются в один отсортированный массив, причем процедура слияния также распараллеливается.

//Слияние двух расположенных рядом друг с другом частей массива
void merge(int *A, int *B, int l, int m, int r)
//A - сортируемый массив, B - буфер для слияния, l - первый элемент первой части, r - последний элемент второй части, m - последний элемент первой части
{
 int i=l;
 int j = m+1;
 int k=l;
 //Вставлять минимальные элементы в B пока не кончится одна из последовательностей
 while (( i<=m) && (j<= r))
 {
  if (A[i]  {
   B[k] = A[i];
   i++;
  } else {
   B[k] = A[j];
   j++;
  }
  k++;
 }
 //Скопировать остаток, если таковой имеется
 while (i < = m)
 {
  B[k]=A[i];
  k++;
  i++;
 }
 while (j < = r)
 {
  B[k]=A[j];
  k++;
  j++;
 }
 //Отсортированная часть остаётся в B
}

//Сортировка слиянием, без рекурсии
void nrmsort(int* A, int* B, int l, int r)
//A - сортируемый массив, B - буфер для слияния, l - левая граница сортируемого участка, r - правая граница
{
 int p=2;
 int m;
 int i;
 int r2;
 int N = r-l+1;
 int *tA = A;
 int *tB = B;
 int *t = NULL;
 
 while(p<(2*N))
 {
  for(i=l;i<=r;i+=p)
  {
   r2 = min(i+p-1,r);
   m = min(r,((i+i+p-1) >> 1)); 
   merge(tA,tB,i,m,r2);
  }
  p *= 2; //Вдвое увеличим размер сливаемых частей
  t = tA; //Поменяем сортируемый массив и буфер местами
  tA = tB;
  tB = t;
  t = NULL;
 }
 if (tA != A)
 {
  //Переписать элементы в исходный массив А
  for (int k = l; k<= r; k++)
  {
   A[k] = B[k];
  }
 }
}

//Сортировка слиянием, распараллеленная
void mp_sort(int* A, int* B, int N, int P)
//A - сортируемый массив, B - буфер для слияния, N - размер массива, P - число параллельно выполняемых потоков

{
 int *tA = A;
 int *tB = B;
 int *t = NULL;
 //1)Разбиение на блоки и сортировка их по отдельности
 int i;
 int part_size = (int)ceil((float)N/(float)P);

 #pragma omp parallel shared(P, tA, tB, N, part_size)
 #pragma omp for private(i)
 for(i=0;i {
  nrmsort(tA,tB,i*part_size,min((i+1)*part_size,N-1));
 }
 int r2,m;
 while (part_size < (2*N))
 {
  #pragma omp parallel shared(P, tA, tB, N, part_size)
  #pragma omp for private(i,r2,m)
  for(i=0;i  {
   r2 = min(i+part_size-1,N-1);
   m = ((i+i+part_size-1) >> 1); 
   merge(tA,tB,i,m,r2);
  }
  part_size *= 2;
  t = tA;
  tA = tB;
  tB = t;
  t = NULL;
 }
 if (tA != A)
 {
  //Переписать элементы в исходный массив А

  int k;
  #pragma omp parallel shared(A,B,N)
  #pragma omp for private(k)
  for (k = 0; k< N; k++)
  {
   A[k] = B[k];
  }
 }
}