title: C++ Merge Sort using iterators
body: <p>Currently, I am trying to create a simple C++ Merge Sort Program.</p>
  <pre><code>using namespace std;
  
  using Iterator = std::vector&lt;int&gt;::iterator;
  using CIterator = std::vector&lt;int&gt;::const_iterator;
  std::vector&lt;int&gt; merge(CIterator left_begin, CIterator left_end, CIterator right_begin, CIterator right_end) {
      std::vector&lt;int&gt; result;
      
      CIterator left = left_begin;
      CIterator right = right_begin;
      
      while (left != left_end &amp;&amp; right != right_end) {
          if (*left &lt;= *right) {
              result.push_back(*left);
              left++;
          } else {
              result.push_back(*right);
              right++;
          }
      }
      
      while (left != left_end) {
          result.push_back(*left);
          left++;
      }
      
      while (right != right_end) {
          result.push_back(*right);
          right++;
      }
      
      return result;
  }
  </code></pre>
  <p>I created a merge function that basically connects two sorted vectors into one and returns it (I am bound to use the following return type of the function merge). Then Trying to write the driver function merge sort I have the following code, that I think works correctly</p>
  <pre><code>void merge_sort(Iterator begin, Iterator end) {
      auto difference = distance(begin, end);
      
      if (difference &lt;= 1) {
          return;
      }
      
      Iterator middle = begin;
      advance(middle, difference / 2);
      
      merge_sort(begin, middle);
      merge_sort(middle, end);
      
      vector&lt;int&gt; result = merge(begin, middle, middle, end);
      // But what to put here?
  }
  </code></pre>
  <p>At the place of the comment mark, I don't understand what to write in order to move the sorted array a step up in the recursion. I tried</p>
  <pre><code>    begin = result.begin();
      end = result.end();
  </code></pre>
  <p>but this obviously doesnt work</p>