title: MergeSort. Implementation with Iterators
body: <p>I need to implement the algorithm of mergesort with following interface:</p>
  
  <pre><code>template &lt;typename T, typename Comp&gt;
  void mergesort(T begin, T end, Comp comp);
  </code></pre>
  
  <p>where <em>begin</em> and <em>end</em> - iterators for elements of some container of type T, comp - is function of comparing elements, which are stored in container. And</p>
  
  <pre><code>template &lt;typename T, typename Comp&gt;
  void merge(T beginLeft, T endLeft, T beginRight, T endRight,
                  T beginResult, Comp comp);
  </code></pre>
  
  <p>is function of merging of two sorted containers (<em>beginLeft</em> and <em>endLeft</em> - iterators of the first container,  <em>beginRight</em> and <em>endRight</em> - of the second) and result should be iterator to the begining of new merged container <em>beginResult</em>.</p>
  
  <p>It should be look like <a href="http://www.cplusplus.com/reference/algorithm/merge/" rel="nofollow">this</a>. </p>
  
  <p>I've wrote recursive function for merge sort, which calls the procedure of merging. </p>
  
  <pre><code>template &lt;typename T, typename Comp&gt;
  void mergesort(T begin, T end, Comp comp)
  {
      if (begin == std::prev(end))
      {
          return;
      }    
  
      T middle = begin + std::distance(begin, end) / 2;
  
      mergesort&lt;T, Comp&gt;(begin, middle, comp);
      mergesort&lt;T, Comp&gt;(middle, end, comp);
  
      merge&lt;T, Comp&gt;(begin, middle, middle, end, begin, comp);
  }
  
  template &lt;typename T, typename Comp&gt;
  void merge(T beginLeft, T endLeft, T beginRight, T endRight,
                  T beginResult, Comp comp)
  {
      while (beginLeft != endLeft &amp;&amp; beginRight != endRight)
      {
          if (comp(*beginLeft, *beginRight))
          {
              *beginResult = *beginLeft;
              ++beginResult;
              ++beginLeft;
          }
          else
          {
              *beginResult = *beginRight;
              ++beginResult;
              ++beginRight;
          }
      }
  
      while (beginLeft != endLeft)
      {
          *beginResult = *beginLeft;
          ++beginResult;
          ++beginLeft;
      } 
      while (beginRight != endRight)
      {
          *beginResult = *beginRight;
          ++beginResult;
          ++beginRight;
      } 
  }
  </code></pre>
  
  <p>Function <em>merge</em> works correctly, but I don't quite understand, how <em>mergesort</em> should work. What argument should I pass to     </p>
  
  <pre><code>merge&lt;T, Comp&gt;(begin, middle, middle, end, /?...?/, comp);
  </code></pre>
  
  <p>If I pass just <em>begin</em> there, than the result of sorting is not correct. Or should I pass there some temporary container. But how can I create it, if I have only type of iterator and don't know the type of elements?</p>
  
  <p>I will be grateful for your help. Thank you!</p>
  
  <p>--ADDED---</p>
  
  <p>Example of merging:</p>
  
  <pre><code>vector&lt;int&gt; vec1;
  vector&lt;int&gt; vec2;
  vector&lt;int&gt; vec3(6);
  vec1.push_back(1);
  vec1.push_back(3);
  vec1.push_back(5);
  vec2.push_back(2);
  vec2.push_back(4);
  vec2.push_back(6);
  merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin(), std::less&lt;int&gt;()); 
  
  for (int i = 0; i &lt; vec3.size(); ++i)
  {
      std::cout &lt;&lt; vec3[i] &lt;&lt; std::endl;
  }
  </code></pre>
  
  <p>Output is: 1 2 3 4 5 6</p>