Why is std::sort() faster than std::make_heap()?
<p>I have <code>13721057</code> elements in my <code>std::vector&lt;Sequence&gt;</code>. I need to sort this vector and grab the first 25 elements. I thought, since you can build a heap in <code>O(N)</code> it must be faster to pop 25 elements (each being <code>O(logN)</code>) than sorting the whole vector in <code>O(NlogN)</code>.</p>

<p>However, when I time the code:</p>

<pre><code>clock_t tStart = clock();
sort(mostFrequent.begin(), mostFrequent.end(), greater&lt;Sequence&gt;());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
</code></pre>

<p>vs.</p>

<pre><code>clock_t tStart = clock();
make_heap(mostFrequent.begin(), mostFrequent.end());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
</code></pre>

<p>It appears to be much faster to sort the whole vector. Why is this?</p>