Friday 19 February 2016

OpenMP Program for Merge Sort

                         In this post, we will see how to implement merge sort concurrently using OpenMP API.
                        OpenMP API is available with gcc/g++ compiler.

Watch following video to know Basics of OpenMP:


Watch following video to know OpenMP Sections which are used to allocate different work to different threads:


                        Go through the following program. Output is given at the end of the program.



Program: (mergesort.c)


#include<stdio.h>
#include<omp.h>

void merge(int array[],int low,int mid,int high)
{
  int temp[30];
  int i,j,k,m; 
  j=low;
  m=mid+1;
  for(i=low; j<=mid && m<=high ; i++)
  {
     if(array[j]<=array[m])
     {
         temp[i]=array[j];
         j++;
     }
     else
     {
         temp[i]=array[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=high; k++)
     {
         temp[i]=array[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        temp[i]=array[k];
        i++;
     }
  }
  for(k=low; k<=high; k++)
     array[k]=temp[k];
}


void mergesort(int array[],int low,int high)
{
 int mid;
 if(low<high)
 {
   mid=(low+high)/2;

   #pragma omp parallel sections num_threads(2) 
    {
      #pragma omp section
        {
          mergesort(array,low,mid);
        }
      
      #pragma omp section
        {
          mergesort(array,mid+1,high);
        }
    }
   merge(array,low,mid,high);
 }
}


int main()
{
 int array[50];
 int i,size;
 printf("Enter total no. of elements:\n");
 scanf("%d",&size);
 printf("Enter %d elements:\n",size);
 for(i=0; i<size; i++)
 {
   scanf("%d",&array[i]);
 }
 mergesort(array,0,size-1);
 printf("Sorted Elements as follows:\n");
 for(i=0; i<size; i++)
    printf("%d ",array[i]);
 printf("\n");
 return 0;
}

How To Run:
To Compile:
gcc -fopenmp mergesort.c

To Run:
./a.out

Output:

Next: OpenMP program for n-ary search algorithm

Previous: Concurrent Quicksort Program in C++ using OPENMP




2 comments:

  1. Some how if I time the program without openmp it is faster than with parallel.
    https://github.com/AP-ATUL/HPC
    Using the input.txt

    ReplyDelete
    Replies
    1. For smaller dataset, this thing happens as for creating threads, allocating tasks take extra time. For large dataset, parallel/concurrent execution with openmp will take less time.

      Delete