Sorting an array in openmp

Question

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;
    }
}

Answer 1

Variables "j" and "k" need to be private on the parallel region. Otherwise you have a data race condition.

Answer 2

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.