I have an array of 100 elements that needs to be sorted with insertion sort using OpenMP. When I parallelize my sort it does not give correct values. Can some one help me
void insertionSort(int a[])
{
int i, j, k;
#pragma omp parallel for private(i)
for(i = 0; i < 100; i++)
{
k = a[i];
for (j = i; j > 0 && a[j-1] > k; j--)
#pragma omp critical
a[j] = a[j-1];
a[j] = k;
}
}
Variables "j" and "k" need to be private on the parallel region. Otherwise you have a data race condition.
Unless it's a homework, sorting as few as 100 elements in parallel makes no sense: the overhead introduced by parallelism will far outweigh any performance benefit.
And, insertion sort algorithm is inherently serial. When a[i] is processed, it is supposed that all previous elemens in the array are already sorted. But if two elements are processed in parallel, there is obviously no such guarantee.
A more detailed explanation of why insertion sort cannot be parallelized in the suggested way is given by @dreamcrash in his answer to a similar question.
