title: C++ Fast Percentile Calculation
body: <p>I'm trying to write a percentile function that takes 2 vectors as input and 1 vector as output. One of the input vector (Distr) would be a distribution of random numbers. The other input vector (Tests) would be a vector of values that I want to calculate the percentile from Distr. The output would be a vector (same size as Tests) that returns the percentile for each value in Tests.</p>
  
  <p>The following is an example of what I want:</p>
  
  <pre><code>Input Distr = {3, 5, 8, 12}
  Input Tests = {4, 9}
  Output Percentile = {0.375, 0.8125}
  </code></pre>
  
  <p>Following is my implementation in C++:</p>
  
  <pre><code>vector&lt;double&gt; Percentile(vector&lt;double&gt; Distr, vector&lt;double&gt; Tests)
  {
      double prevValue, nextValue;
      vector&lt;double&gt; result;
      unsigned distrSize = Distr.size();
  
      std::sort(Distr.begin(), Distr.end());
  
      for (vector&lt;double&gt;::iterator test = Tests.begin(); test != Tests.end(); test++)
      {
  
          if (*test &lt;= Distr.front())
          {
              result.push_back((double) 1 / distrSize); // min percentile returned (not important)
          }
          else if (Distr.back() &lt;= *test)
          {
              result.push_back(1); // max percentile returned (not important)
          }
          else
          {
              prevValue = Distr[0];
              for (unsigned sortedDistrIdx = 1; sortedDistrIdx &lt; distrSize; sortedDistrIdx++)
              {
                  nextValue = Distr[sortedDistrIdx];
  
                  if (nextValue &lt;= *test)
                  {
                      prevValue = nextValue;
                  }
                  else
                  {
                      // linear interpolation
                      result.push_back(((*test - prevValue) / (nextValue - prevValue) + sortedDistrIdx) / distrSize);
                      break;
                  }
              }
          }
      }
      return result;
  }
  </code></pre>
  
  <p>The size of both Distr and Tests can be from 2,000 to 30,000.</p>
  
  <p>Are there any existing libraries that can calculate percentile as shown above (or similar)? If not how can I make the above code faster?</p>