title: C++ "terminating with uncaught exception of type std::out_of_range: vector" error in a merge sort algorithm
body: <p>I have a c++ code which should use merge sort algorithm to sort a file containing 800,000+ words each on a new line. </p>
  
  <p><strong>What I did ?</strong></p>
  
  <p>To start off, I tried implementing the following merge sort algorithm and tried testing it on a small piece of input. I cannot figure out where I am getting index out of bounds error with the vector. If anyone could help me with this, I would really appreciate</p>
  
  <pre><code>#include &lt;fstream&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  using namespace std;
  
  
  vector&lt;string&gt; merge(const vector&lt;string&gt;&amp; first,
                       const vector&lt;string&gt;&amp; second) {
      // Write your code to merge vectors first and
      // second onto result.
  
      vector&lt;string&gt; output;
      int i = 0;
      int j = 0 ;
      int size_first = sizeof(first);
      int size_second = sizeof(second);
  
      while(i &lt; size_first || j &lt; size_second){
          if (i &lt; size_first &amp;&amp; j &lt; size_second){
              if (first.at(i) &lt; second.at(j)){
                  output.push_back(first.at(i));
                  i++;
              }
              else{
                  output.push_back(second.at(i));
                  j++;
              }
          }
          else if (i &lt; size_first){
              output.push_back(first.at(i));
              i++;
          }
          else{
              output.push_back(second.at(j));
              j++;
          }
  
      }
      return output;
  }
  
  void mergeSort(vector&lt;string&gt;&amp; words) {
      if (words.size() &lt;= 1)
      {
          return;
      }
      int n = words.size();
      int middle = n/2;
  
      vector&lt;string&gt; first_half(middle);
      for (int i = 0; i &lt; middle; ++i) {
          first_half[i] = words[i];
      }
  
      vector&lt;string&gt; second_half(n - middle);
      for (int i = middle; i &lt; n; ++i) {
          second_half[i - middle] = words[i];
      }
  
      words = merge(first_half, second_half);
  }
  
  void sort(vector&lt;string&gt;&amp; words) {
  
      // Invoke mergeSort  here.
      mergeSort(words);
  }
  
  int main(){
  
      vector&lt;string&gt; names;
      names.push_back("Smith");
      names.push_back("Abinash");
      names.push_back("Ciara");
      names.push_back("Reeta");
  
      sort(names);
  
      return 0;
  
  }
  </code></pre>