Mergesort Parallel Program

2. Using OpenMP, implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<time.h>
void mergesort(int,int);
void merge(int,int,int);
int a[100000];
void main()
{
 int n,i;
 clock_t start,end;
 printf("\n\n....MERGESORT PARALLEL PROGRAM....\n\n");
 printf("\n\nEnter the element to be sorted\n\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
   a[i]=rand()%100;
 printf("\n Array element to be sorted \n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 start=clock();
 mergesort(0,n-1);
 end=clock();
 printf("\n\n The sorted elements are\n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 printf("\n\n The time taken is %f\n",(double)(end-start)/CLOCKS_PER_SEC);
 printf("\n\n****...........*******\n\n");
}
void mergesort(int low,int high)
{
 int mid;
 if(low<high)
  {
   mid=(low+high)/2;
   #pragma omp parallel section
    {
     #pragma omp section
     mergesort(low,mid);
     #pragma omp section
     mergesort(mid+1,high);
    }
   merge(low,mid,high);
  }
}
void merge(int low,int mid,int high)
 {
  int i,j,h,k,b[100000];
  h=low;
  i=low;
  j=mid+1;
  while((h<=mid)&&(j<=high))
   {
    if(a[h]<a[j])
     {
      b[i]=a[h];
      h=h+1;
     }
    else
     {
      b[i]=a[j];
      j=j+1;
     }
    i=i+1;
   }
 if(h>mid)
  {
   for(k=j;k<=high;k++)
     {
  b[i]=a[j];
  i=i+1;
     }
  }
else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i=i+1;
  }
 }
 for(k=low;k<=high;k++)
   a[k]=b[k];
}



OUTPUT:

Enter the number of elements to be sorted
6

Array elements to be sorted are
83  86  77  15  93  35