title: CUDA Thrust and sort_by_key
body: <p>I’m looking for a sorting algorithm on CUDA that can sort an array A of elements (double) and returns an array of keys B for that array A.
  I know the <code>sort_by_key</code> function in the Thrust library but I want my array of elements A to remain unchanged.
  What can I do?</p>
  
  <p>My code is:</p>
  
  <pre><code>void sortCUDA(double V[], int P[], int N) {
  
          real_t *Vcpy = (double*) malloc(N*sizeof(double));
          memcpy(Vcpy,V,N*sizeof(double));
  
          thrust::sort_by_key(V, V + N, P);
          free(Vcpy);
  }
  </code></pre>
  
  <p>i'm comparing the thrust algorithm against others that i have on sequencial cpu</p>
  
  <pre><code>N               mergesort       sortCUDA
  113             0.000008        0.000010
  226             0.000018        0.000016
  452             0.000036        0.000020
  905             0.000061        0.000034
  1810            0.000135        0.000071
  3621            0.000297        0.000156
  7242            0.000917        0.000338
  14484           0.001421        0.000853
  28968           0.003069        0.001931
  57937           0.006666        0.003939
  115874          0.014435        0.008025
  231749          0.031059        0.016718
  463499          0.067407        0.039848
  926999          0.148170        0.118003
  1853998         0.329005        0.260837
  3707996         0.731768        0.544357
  7415992         1.638445        1.073755
  14831984        3.668039        2.150179
  115035495       39.276560       19.812200
  230070990       87.750377       39.762915
  460141980       200.940501      74.605219
  </code></pre>
  
  <p>Thrust performance is not bad, but I think if I use OMP can probably get easily a better CPU time</p>
  
  <p>I think this is because to memcpy</p>
  
  <p>SOLUTION: </p>
  
  <pre><code>void thrustSort(double V[], int P[], int N)
  {
          thrust::device_vector&lt;int&gt; d_P(N);
          thrust::device_vector&lt;double&gt; d_V(V, V + N);
          thrust::sequence(d_P.begin(), d_P.end());
  
          thrust::sort_by_key(d_V.begin(), d_V.end(), d_P.begin());
  
          thrust::copy(d_P.begin(),d_P.end(),P);
  }
  </code></pre>
  
  <p>where V is a my double values to sort</p>