title: C++ parallel sort
body: <p>I need to sort data blocks which are stored in an array of structures. Structures have no pointers. Each block has its counter number and coordinates of the place in an array where the data block equal to the structure block is. For example if we have a data array which we can divide in 4 blocks of NxN, we have 4 structure blocks in index array of structure blocks and each of them has its own number and position in data array with the help of which we can compute the pointer of the block in data array using index block. Sorting should be done with the comparer that compares two blocks in such way that the least of two blocks shold have least i-th number of data. For example comparer:</p>
  
  <pre><code>for( i = 0; i &lt; N * N; ++i )
  {
      if( a[i] &lt; b[i] ) return -1;
      if( a[i] &gt; b[i] ) return 1;
  }
  </code></pre>
  
  <p>where <code>a</code> and <code>b</code> are pointers to the blocks of data array which we can get due to index array and pointer of the start of data array.
  Sorting shouldn't sort data array but index array.
  So the question is: what parallel algorithm can I use (except frameworks, libraries, I need exactly algorithms or standard language kits, like pthread or qt libs, or c/c++ standard libs) to avoid synchronization errors? The code or pseudocode would be helpful too.</p>