title: Why does std::nth_element return sorted vectors for input vectors with N < 33 elements?
body: <p>I am using <code>std::nth_element</code> to get a (roughly correct) value for a percentile of a vector, like so:</p>
  
  <pre><code>double percentile(std::vector&lt;double&gt; &amp;vectorIn, double percent)
  {
      std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end());
  
      return vectorIn[(percent*vectorIn.size())/100];
  }  
  </code></pre>
  
  <p>I noticed that for vectorIn lengths of up to 32 elements, the vector gets completely sorted. Starting from 33 elements it is never sorted (as expected).</p>
  
  <p>Not sure whether this matters but the function is in a "(Matlab-)mex c++ code" that is compiled via Matlab using the "Microsoft Windows SDK 7.1 (C++)".</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>Also see the following histogram of the lengths of the longest sorted blocks in 1e5 vectors passed to the function (vectors contained 1e4 random elements and a random percentile was calculated). Note the peak at very small values.</p>
  
  <p><img src="https://i.stack.imgur.com/kZPs3.png" alt="Histogram of lengths of longes sorted blocks"></p>