title: Sorting an array in openmp - critical section
body: <p>Quite similar to that question 
  <a href="https://stackoverflow.com/questions/5904959/sorting-an-array-in-openmp">Sorting an array in openmp</a>
  which has several hundred views but no correct answer. Therefore I give it another try asking here again.
  I am aware of the overhead and uselessness of this regarding speedup or performance. It simply is a small example to get into openMP. The fact that is is insertSort is given by my courseinstructor.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>std::vector&lt;int&gt; insertionSort(std::vector&lt;int&gt; a) {
      int i, j, k;
      #pragma omp parallel for private(i,j,k)
      for(i = 0; i &lt; a.size(); i++) {
      #pragma omp critical
          k = a[i];
          for (j = i; j &gt; 0 &amp;&amp; a[j-1] &gt; k; j--)
  
          #pragma omp critical
          {
              a[j] = a[j-1];
              a[j] = k;
          }
      }
   return a;
   }
  </code></pre>
  
  <p>I understand that the critical aspect is the race-condition between threads accessing (reading and writing) elements of a - that is, why I put a critical section arround all of them. That does not seem to be sufficient. What am I missing here. Without the pragmas, the sorting is correct.</p>