title: Move items to the front of an array
body: <p>I have items in the centre of an array and I want to move them to the front of this array. For example:</p>
  
  <pre><code>array[8] = {10, 38, 38, 0, 8, 39, 10, 22}
  </code></pre>
  
  <p>and I have an index array</p>
  
  <pre><code>index[6] = {0, 3, 4, 6, 7, 1}
  </code></pre>
  
  <p>and I want to move these 6 items to the front of the array</p>
  
  <pre><code>result[8] = {10, 0, 8, 10, 22, 38, 38, 39}
  </code></pre>
  
  <p>Actually the order doesn't matter, just make sure the item whose index is in the index array should always before the item whose index is not in the index array.</p>
  
  <p>Can anyone give me a fast algorithm? Actually this is one step in an KNN problem, the data array could be very large. The algorithm should run as fast as possible and the extra space needed should be as small as possible. It is better if you can give me CUDA implementation.</p>
  
  <p><strong>Update</strong>: Compare to the data array, the size of the index array is very small. In my case, it is only about 200.</p>
  
  <p><strong>Update</strong>: Please note that the size of the data array could be very very very large! It goes to 1M, 10M even higher(The data array is loaded to GPU memory which is quite limited). Any algorithm needs a temp array which has the same size with data array is not acceptable.</p>