Объединить сортировку с OpenMP

Question

Итак, я делаю программу, которая сортирует aryay с 100.000.000 целыми числами, используя алгоритм сортировки слиянием.В конце программа выводит, сколько времени потребовалось, чтобы отсортировать массив и найти его наибольший элемент с 1,2,3 и 4 потоками.«Время слияния» кажется правильным: один поток является самым медленным, а четыре потока - самым быстрым, как и ожидалось (t1> t2> t3> t4), но это соотношение не применимо для времени «find max».Любые идеи, почему это происходит?

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <omp.h>
#include <unistd.h>
#define MAX 100000000
#define MAX_THREAD 4

typedef struct thr {
    int thr_low;
    int thr_high;
}thr_t;

void merge(int low, int mid, int high);
void merge_sort(int low, int high);
void multi_merge_sort(int low,int high);
void copyArray(int *A,int begin,int end,int *B);

int *A,*B,found,greatest,num=1,dummy;
double mergetime[4],findmax[4],start_time,maxtime;


int main(int argc, char const *argv[]){

  A= malloc(sizeof(int) * MAX);
  B= malloc(sizeof(int) * MAX);


  for (int i = 0; i < MAX; i++) {
    B[i] = rand() ;
    if(B[i]>greatest)
    greatest=B[i];
  }
  do{
    copyArray(A,0,MAX,B);

    thr_t *thr;
    thr_t thrlist[num];
    int len = MAX / num;

    int low = 0;
    found = greatest = dummy = 0;

    for (int i = 0; i < num; i++, low += len) {
        thr = &thrlist[i];

        thr->thr_low = low;
        thr->thr_high = low + len - 1;
        if (i == (num - 1))
          thr->thr_high = MAX - 1;
     }

    start_time=omp_get_wtime();

    #pragma omp parallel num_threads(num)
    {
      int ID = omp_get_thread_num();
      thr_t *thr = &thrlist[ID];
      int low = thr->thr_low ;
      int high = thr->thr_high;
      multi_merge_sort(low,high);
    }

    thr_t *thrm = &thrlist[0];
    for (int i = 1; i < num; i++) {
        thr_t *thr = &thrlist[i];
        merge(thrm->thr_low, thr->thr_low - 1, thr->thr_high);
    }

    mergetime[(num-1)]=omp_get_wtime()-start_time;
    num++;
  }while(num<=MAX_THREAD);





printf("Merge time:\n");
  for (int i = 0; i < 4; i++) {
    printf("%d --> %lf sec\n",(i+1),mergetime[i]);
  }
  printf("\n");
  printf("Found greatest num in:\n");
  for (int i = 0; i < 4; i++)
    printf("%d --> %lf sec\n",(i+1),findmax[i]);

  free(A);
  free(B);
  return 0;
}



void merge(int low, int mid, int high){

  int p1 = mid - low + 1;
  int p2 = high - mid;

  int *left = malloc(p1 * sizeof(int));
  int *right = malloc(p2 * sizeof(int));

  int i,j,k=low;

  for (i = 0; i < p1; i++){
    left[i] = A[i + low];

    if(greatest==left[i] && found==0){
      found =1;
      findmax[(num-1)]=omp_get_wtime()-start_time;
    }
  }

  for (i = 0; i < p2; i++){
      right[i] = A[i + mid + 1];
      if(greatest==right[i] && found==0){
        found =1;
        findmax[(num-1)]=omp_get_wtime()-start_time;
      }
    }

  i = j = 0;

  while (i < p1 && j < p2) {
    if (left[i] <= right[j])
      A[k++] = left[i++];
    else
      A[k++] = right[j++];
  }

  while (i < p1)
    A[k++] = left[i++];

  while (j < p2)
    A[k++] = right[j++];

  free(left);
  free(right);
}

void merge_sort(int low, int high){

  int mid = low + (high - low) / 2;

  if (low < high) {
    merge_sort(low, mid);

    merge_sort(mid + 1, high);

    merge(low, mid, high);
  }
}

void multi_merge_sort(int low,int high){

  int mid = low + (high - low) / 2;

  if (low < high) {
    merge_sort(low, mid);
    merge_sort(mid + 1, high);
    merge(low, mid, high);
  }
}

void copyArray(int *A,int begin,int end,int *B){
  int k=0;
  for(int i = begin; i < end; i++){
     A[i] = B[i];
  } 
}