title: Parallel Merge-Sort in OpenMP
body: <p>I have seen an algorithm for parallel merge-sort in a <a href="https://arxiv.org/pdf/1403.8006.pdf" rel="nofollow noreferrer">this</a> paper. This is the code:</p>
  <pre><code>void mergesort_parallel_omp (int a[], int size, int temp[], int threads) 
  {  
      if ( threads == 1)       { mergesort_serial(a, size, temp); }
      else if (threads &gt; 1) 
      {
           #pragma omp parallel sections
           {
               #pragma omp section
               mergesort_parallel_omp(a, size/2, temp, threads/2);
               #pragma omp section
               mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2, threads - threads/2);
           }
           merge(a, size, temp); 
      } // threads &gt; 1
  }
  </code></pre>
  <p>I run it on a multicore. What happens is that at the leafs of the tree, 2 threads run in parallel. After they finished their work 2 other threads start and so on. Even if we have free cores for all the leaf nodes.</p>
  <p>I think the reason is this OpenMP code does not create parallel regions inside parallel regions. Am I correct?</p>