title: OpenMP : Parallel QuickSort
body: <p>I try to use OpenMP to parallelize QuickSort in partition part and QuickSort part. My C code is as follows:</p>
  <pre><code>#include &quot;stdlib.h&quot;
  #include &quot;stdio.h&quot;
  #include &quot;omp.h&quot;
  
  // parallel partition
  int ParPartition(int *a, int p, int r) {
      int b[r-p];
      int key = *(a+r); // use the last element in the array as the pivot
      int lt[r-p]; // mark 1 at the position where its element is smaller than the key, else 0
      int gt[r-p]; // mark 1 at the position where its element is bigger than the key, else 0
      int cnt_lt = 0; // count 1 in the lt array
      int cnt_gt = 0; // count 1 in the gt array
      int j=p;
      int k = 0; // the position of the pivot
      // deal with gt and lt array
      #pragma omp parallel for
      for ( j=p; j&lt;r; ++j) {
          b[j-p] = *(a+j);
          if (*(a+j) &lt; key) {
              lt[j-p] = 1;
              gt[j-p] = 0;
          } else {
              lt[j-p] = 0;
              gt[j-p] = 1;
          }
      }
      // calculate the new position of the elements
      for ( j=0; j&lt;(r-p); ++j) {
          if (lt[j]) {
              ++cnt_lt;
              lt[j] = cnt_lt;
          } else
              lt[j] = cnt_lt;
          if (gt[j]) {
              ++cnt_gt;
              gt[j] = cnt_gt;
          } else
              gt[j] = cnt_gt;
      }
      // move the pivot
      k = lt[r-p-1];
      *(a+p+k) = key;
      // move elements to their new positon
      #pragma omp parallel for 
      for ( j=p; j&lt;r; ++j) {
          if (b[j-p] &lt; key)
              *(a+p+lt[j-p]-1) = b[j-p];
          else if (b[j-p] &gt; key)
              *(a+k+gt[j-p]) = b[j-p];
      }
      return (k+p);
  }
  
  void ParQuickSort(int *a, int p, int r) {
      int q;
      if (p&lt;r) {
          q = ParPartition(a, p, r);
          #pragma omp parallel sections
          {
          #pragma omp section
          ParQuickSort(a, p, q-1);
          #pragma omp section
          ParQuickSort(a, q+1, r);
          }
      }
  }
  
  int main() {
      int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6};
      ParQuickSort(a, 0, 9);
      int i=0;
      for (; i!=10; ++i)
          printf(&quot;%d\t&quot;, a[i]);
      printf(&quot;\n&quot;);
      return 0;
  }
  </code></pre>
  <p>For the example in the main function, the sorting result is:</p>
  <pre><code>0   9   9   2   2   2   6   7   7   7
  </code></pre>
  <p>I used gdb to debug. In the early recursion, all went well. But in some recursions, it suddenly messed up to begin duplicate elements. Then generate the above result.</p>
  <p>Can someone help me figure out where the problem is?</p>