title: Why do these two variations on the "quick sorting" algorithm differ so much in performance?
body: <p>I initially thought up some sorting algorithm to code in C++ for practice. People told me it's very inefficient (indeed, sorting a few hundred numbers took ~10 seconds). The algorithm was to remember the first element ("pivot") in a vector, then parse through every other element, moving each element to the left of the pivot if it is smaller, or not do anything otherwise. This would split the list into to smaller lists to sort; the rest is done through recursion. </p>
  
  <p>So now I know that dividing the list into two and doing recursions like this is essentially what quicksorting does (although there are a lot of variations on how to do the partitioning). I didn't understand why my original code was so inefficient, so I wrote up a new one. Someone had mentioned that it is because of the insert() and erase() functions, so I made sure to not use those, but instead used swap().</p>
  
  <p>Old (slow):</p>
  
  <pre><code>void sort(vector&lt;T&gt;&amp; vec){
    int size = vec.size();
    if (size &lt;= 1){ //this is the most basic case
      return;
    }
  
    T pivot = vec[0];
    int index = 0; //to help split the list later
    for (int i = 1; i &lt; size; ++i){ //moving (or not moving) the elements
      if (vec[i] &lt; pivot){
        vec.insert(vec.begin(), vec[i]);
        vec.erase(vec.begin() + i + 1);
        ++index;
      }
    }
  
    if (index == 0){ //in case the 0th element is the smallest
      vec.erase(vec.begin());
      sort(vec);
      vec.insert(vec.begin(), pivot);
    }
    else if(index == size - 1){ //in case the 0th element is the largest
      vec.pop_back();
      sort(vec);
      vec.push_back(pivot);
    }
  
    //here is the main recursive portion
    vector&lt;T&gt; left = vector&lt;T&gt;(vec.begin(), vec.begin() + index);
    sort(left);
    vector&lt;T&gt; right = vector&lt;T&gt;(vec.begin() + index + 1, vec.end());
    sort(right);
  
    //concatenating the sorted lists together
    left.push_back(pivot);
    left.insert(left.end(), right.begin(), right.end());
  
    vec = left;
  }
  </code></pre>
  
  <p>new (fast):</p>
  
  <pre><code>template &lt;typename T&gt;
  void quickSort(vector&lt;T&gt;&amp; vec, const int&amp; left, const int&amp; right){
    if (left &gt;= right){ //basic case
      return;
    }
    T pivot = vec[left];
    int j = left; //j will be the final index of the pivot before the next iteration
  
    for (int i = left + 1; i &lt;= right; ++i){
      if (vec[i] &lt; pivot){
        swap(vec[i], vec[j]); //swapping the pivot and lesser element
        ++j;
        swap(vec[i], vec[j]); //sending the pivot next to its original spot so it doesn't go the to right of any greater element
      }
    }
  
    //recursion
    quickSort(vec, left, j - 1);
    quickSort(vec, j + 1, right);
  }
  </code></pre>
  
  <p>The difference in performance is insane; the newer version can sort through tens of thousands of numbers in less than a second, while the first one can't do that with 100 numbers. What are erase() and insert() doing to slow it down, exactly? Is it really the erase() and insert() causing the bottleneck, or is there something else I am missing?</p>