//Слияние двух расположенных рядом друг с другом частей массива
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