title: Sort array of n elements which has k sorted sections
body: <p>What is the best way to sort an section-wise sorted array as depicted in the second image?</p>
  
  <p>The problem is performing a quick-sort using <a href="https://en.wikipedia.org/wiki/Message_Passing_Interface" rel="nofollow noreferrer">Message Passing Interface</a>. The solution is performing quick-sort on array sections obtained by using <code>MPI_Scatter()</code> then joining the sorted 
  pieces using <code>MPI_Gather()</code>.</p>
  
  <p><a href="https://i.stack.imgur.com/9ni3C.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9ni3C.png" alt="FLOW"></a></p>
  
  <p>Problem is that the array as a whole is unsorted but sections of it are.</p>
  
  <p>Merging the sub-sections similarly to <a href="https://stackoverflow.com/questions/47146881/merge-k-sorted-arrays">this solution</a> seems like the best way of sorting the array, but considering that the sub-arrays are already within a single array other sorting algorithms may prove better.</p>
  
  <p>The inputs for a sort function would be the array, it's length and the number of equally sorted sub-sections. 
  A signature would look something like <code>int* sort(int* array, int length, int sections);</code></p>
  
  <p>The <code>sections</code> parameter can have any value between 1 and 25. The <code>length</code> parameter value is greater than 0, a multiple of <code>sections</code> and smaller than 2^32.</p>
  
  <p><a href="https://i.stack.imgur.com/DCCkD.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DCCkD.png" alt="array"></a></p>
  
  <p>This is what I am currently using:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>int* merge(int* input, int length, int sections)
  {
      int* sub_sections_indices = new int[sections];
      int* result = new int[length];
  
      int section_size = length / sections;
  
      for (int i = 0; i &lt; sections; i++) //initialisation
      {
          sub_sections_indices[i] = 0;
      }
      int min, min_index, current_index;
  
  
      for (int i = 0; i &lt; length; i++) //merging
      {
          min_index = 0;
          min = INT_MAX;
          for (int j = 0; j &lt; sections; j++)
          {
              if (sub_sections_indices[j] &lt; section_size)
              {
                  current_index = j * section_size + sub_sections_indices[j];
                  if (input[current_index] &lt; min)
                  {
                      min = input[current_index];
                      min_index = j;
                  }
              }
          }
          sub_sections_indices[min_index]++;
          result[i] = min;
      }
  
      return result;
  }
  </code></pre>