title: Why is my n log(n) heapsort slower than my n^2 selection sort
body: <p>I have implemented two algorithms for sorting elements from highest to lowest. </p>
  
  <p>The first one, takes quadratic time on the real RAM model and the second an O(n log(n)) time. 
  The second one uses priority queues to get the reduction.</p>
  
  <p>Here are the timings, which are the output of the above program. </p>
  
  <ul>
  <li>the first column is the size of the random array of integers</li>
  <li>the second column is the time in seconds for the O(n^2) technique</li>
  <li><p>the third column is the time in seconds for the O(n log(n)) technique</p>
  
  <pre><code> 9600  1.92663      7.58865
   9800  1.93705      7.67376
  10000  2.08647      8.19094
  </code></pre></li>
  </ul>
  
  <p>In spite of this great difference in complexity, the 3rd column is larger than the second for the array sizes considered. Why is this so? Is the priority queue implementation of C++ slow?</p>
  
  <p>I executed this code on Windows 7, Visual Studio 2012 32-bit. </p>
  
  <p>Here is the code,</p>
  
  <pre><code>#include "stdafx.h"
  #include &lt;iostream&gt;
  #include &lt;iomanip&gt;
  #include &lt;cstdlib&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;queue&gt;
  #include &lt;Windows.h&gt;
  #include &lt;assert.h&gt;
  
  using namespace std;
  
  double time_slower_sort(vector&lt;int&gt;&amp; a) 
  {
      LARGE_INTEGER frequency, start,end;
      if (::QueryPerformanceFrequency(&amp;frequency) == FALSE  ) exit(0);
      if (::QueryPerformanceCounter(&amp;start)       == FALSE  ) exit(0);
  
      for(size_t i=0 ; i &lt; a.size() ; ++i)  
      {
  
          vector&lt;int&gt;::iterator it = max_element( a.begin() + i ,a.end() ) ;
          int max_value = *it; 
          *it = a[i];
          a[i] = max_value;    
  
      }
      if (::QueryPerformanceCounter(&amp;end) == FALSE) exit(0);
      return static_cast&lt;double&gt;(end.QuadPart - start.QuadPart) / frequency.QuadPart;
  }
  
  
  
  double time_faster_sort(vector&lt;int&gt;&amp; a) 
  {
      LARGE_INTEGER frequency, start,end;
      if (::QueryPerformanceFrequency(&amp;frequency) == FALSE  ) exit(0);
      if (::QueryPerformanceCounter(&amp;start)       == FALSE  ) exit(0);
  
  
      // Push into the priority queue. Logarithmic cost per insertion = &gt; O (n log(n)) total insertion cost
      priority_queue&lt;int&gt; pq;
      for(size_t i=0 ; i&lt;a.size() ; ++i)
      {
          pq.push(a[i]);
      }
  
      // Read of the elements from the priority queue in order of priority
      // logarithmic reading cost per read =&gt; O(n log(n)) reading cost for entire vector
      for(size_t i=0 ; i&lt;a.size() ; ++i)
      {
          a[i] = pq.top();
          pq.pop();
      }
      if (::QueryPerformanceCounter(&amp;end) == FALSE) exit(0);
      return static_cast&lt;double&gt;(end.QuadPart - start.QuadPart) / frequency.QuadPart;
  
  }
  
  
  
  
  int main(int argc, char** argv)
  {
      // Iterate over vectors of different sizes and try out the two different variants
      for(size_t N=1000; N&lt;=10000 ; N += 100 ) 
      {
  
          // initialize two vectors with identical random elements
          vector&lt;int&gt; a(N),b(N);
  
          // initialize with random elements
          for(size_t i=0 ; i&lt;N ; ++i) 
          {
              a[i] = rand() % 1000; 
              b[i] = a[i];
          }
  
          // Sort the two different variants and time them  
          cout &lt;&lt; N &lt;&lt; "  " 
               &lt;&lt; time_slower_sort(a) &lt;&lt; "\t\t" 
               &lt;&lt; time_faster_sort(b) &lt;&lt; endl;
  
          // Sanity check
          for(size_t i=0 ; i&lt;=N-2 ; ++i) 
          {
              assert(a[i] == b[i]); // both should return the same answer
              assert(a[i] &gt;= a[i+1]); // else not sorted
          }
  
      }
      return 0;
  }
  </code></pre>