title: Performance gap between sorting a list and a vector of structs. C++
body: <p>I wrote a simple C++ code to check the speed of sorting data , represented in the form of a list and then a vector. </p>
  
  <p>In the case of the list I am getting time as 27 seconds. For a vector I get 10 seconds. Why the huge performance gap? Aren't the algorithms used for sorting the list and the vector the same? viz. mergesort? </p>
  
  <p><em><strong>EDIT:</em></strong> I may be wrong on the last point. As I know, textbooks when descirbing sorting algorithms theoretically, seem to be use the word <code>list</code> in the sense of a <code>std::vector</code>. I don't know how
  how sorting algorithms for vectors would be different from sorting algorithms for lists, so if some one could clarify that would be really helpful. Thank you. </p>
  
  <pre><code> //In this code we compare the sorting times for lists and vectors.
  //Both contain a sequence of structs
  
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;list&gt;
  #include &lt;algorithm&gt;
  #include &lt;time.h&gt;
  #include &lt;math.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;iomanip&gt;
  using namespace std;
  
  
  struct particle
  {
    double x;
    double y;
    double z;
    double w;
  
      bool operator&lt;(const particle&amp; a) const
      {
          return x &lt; a.x;
      }
  
  };
  
  
  int main(int argc, char *argv[])
  {
    int N=20000000;
    clock_t start,stop;
  
    vector&lt;particle&gt; myvec(N);
    vector&lt;particle&gt;::iterator cii;
    //Set vector values
    for (cii = myvec.begin(); cii != myvec.end(); ++cii)
    {
      cii-&gt;x =1.0*rand()/RAND_MAX;
      cii-&gt;y =1.0*rand()/RAND_MAX;
      cii-&gt;z =1.0*rand()/RAND_MAX;
      cii-&gt;w =1.0*rand()/RAND_MAX;
   }
  
  
    list&lt;particle&gt; mylist(N);
    list&lt;particle&gt;::iterator dii;
  
     //Set list values
    for (cii=myvec.begin(),dii = mylist.begin(); dii != mylist.end() &amp;&amp; cii!=myvec.end(); ++dii, ++cii)
    {
        dii-&gt;x =cii-&gt;x;
        dii-&gt;y =cii-&gt;y;
            dii-&gt;z =cii-&gt;z;
        dii-&gt;w =cii-&gt;w;
   }
  
  
    //Sort the vector 
  
    start=clock();
    sort(myvec.begin(),myvec.end());
    stop=clock();
    cout&lt;&lt;"Time for sorting vector "&lt;&lt;(stop-start)/(double) CLOCKS_PER_SEC&lt;&lt;endl;
  
  
  
    //Sort the list
    start=clock();
    mylist.sort();
    stop=clock();
    cout&lt;&lt;"Time for sorting list "&lt;&lt;(stop-start)/(double) CLOCKS_PER_SEC&lt;&lt;endl;
  
  
  
    return 0;
  }
  </code></pre>