title: Is there a specialized algorithm, faster than quicksort, to reorder data ACEGBDFH?
body: <p>I have some data coming from the hardware. Data comes in blocks of 32 bytes, and there are potentially millions of blocks. Data blocks are scattered in two halves the following way (a letter is one block):</p>
  
  <pre><code>A C E G I K M O B D F H J L N P
  </code></pre>
  
  <p>or if numbered</p>
  
  <pre><code>0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
  </code></pre>
  
  <p>First all blocks with even indexes, then the odd blocks. Is there a specialized algorithm to reorder the data correctly (alphabetical order)?</p>
  
  <p>The constraints are mainly on space. I don't want to allocate another buffer to reorder: just one more block. But I'd also like to keep the number of moves low: a simple quicksort would be O(NlogN). Is there a faster solution in O(N) for this special reordering case? </p>