title: Merge Sort Implementation using C++
body: <p>I am having trouble with trying to implement the merge sort algorithm. I would appreciate it if someone can help me out. Here is what I have.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;deque&gt;
  using size_type = std::deque&lt;int&gt;::size_type;
  void print(std::deque&lt;int&gt; &amp;v)
  {
      for(const auto &amp;ref:v)
          std::cout &lt;&lt; ref &lt;&lt; " ";
      std::cout &lt;&lt; std::endl;
  }
  void merge(std::deque&lt;int&gt; &amp;vec, size_type p, size_type q, size_type r)
  {
      int n_1 = q - p;
      int n_2 = r - q;
      std::deque&lt;int&gt; left, right;
      for(auto i = 0; i != n_1; i++)
          left.push_back(vec[p + i]);
      for(auto j = 0; j != n_2; j++)
          right.push_back(vec[q + j]);
      int i = 0, j = 0;
      std::cout &lt;&lt; "left = ";
      print(left);
      std::cout &lt;&lt; "right = ";
      print(right);
      for(auto k = p; k != r; k++) {
          if(i &lt; n_1 &amp;&amp; left[i] &lt;= right[j]) {
              vec[k] = left[i];
              i++;
          }
          else if(j &lt; n_2){
              vec[k] = right[j];
              j++;
          }
      }
  }
  void merge_sort(std::deque&lt;int&gt; &amp;A, size_type p, size_type r)
  {
      int q;
      if(p &lt; r) {
          q = (p + r)/2;
          merge_sort(A, p, q);
          merge_sort(A, q + 1, r);
          merge(A, p, q, r);
      }
  }
  int main()
  {
      std::deque&lt;int&gt; small_vec = {1, 6, 2, 10, 5, 2, 12, 6};
      std::deque&lt;int&gt; samp_vec = {2, 9, 482, 72, 42, 3, 4, 9, 8, 73, 8, 0, 98, 72, 473, 72, 3, 4, 9, 7, 6, 5, 6953, 583};
      print(small_vec);
      merge_sort(small_vec, 0, small_vec.size());
      print(small_vec);
      return 0;
  }
  </code></pre>
  
  <p>The output from the program is:</p>
  
  <pre><code>left = 
  right = 1 
  left = 1 
  right = 6 
  left = 
  right = 10 
  left = 1 6 
  right = 2 10 
  left = 
  right = 2 
  left = 
  right = 6 
  left = 2 
  right = 12 6 
  left = 1 2 6 10 
  right = 5 2 12 6 
  1 2 5 2 6 10 12 6 
  </code></pre>