Merge Sort implemented using iterators #include &lt;iterator&gt;
#include &lt;memory&gt;
#include &lt;algorithm&gt;

template&lt;typename RandomIt&gt;
void sub_merge(RandomIt begin, RandomIt mid, RandomIt end) {
  // create copy of input array;
  const auto left_size = std::distance(begin, mid);
  const auto right_size = std::distance(mid, end);

  auto left = std::make_unique&lt;typename std::iterator_traits&lt;RandomIt&gt;::value_type[]&gt;(left_size);
  auto right = std::make_unique&lt;typename std::iterator_traits&lt;RandomIt&gt;::value_type[]&gt;(right_size);

  const auto left_begin = left.get();
  const auto left_end = left_begin + left_size;
  const auto right_begin = right.get();
  const auto right_end = right_begin + right_size;

  std::copy(begin, mid, left_begin);
  std::copy(mid, end, right_begin);

  // merge until one array is completed
  auto left_iter = left_begin;
  auto right_iter = right_begin;
  auto arr_iter = begin;

  while (left_iter &lt; left_end &amp;&amp; right_iter &lt; right_end) {
    if (*left_iter &lt; *right_iter) {
      *arr_iter = *left_iter;
      left_iter++;
    } else {
      *arr_iter = *right_iter;
      right_iter++;
    }
    arr_iter++;
  }

  // copy remaining array over
  std::copy(right_iter, right_end, arr_iter);
  std::copy(left_iter, left_end, arr_iter);
}

template&lt;typename RandomIt&gt;
void merge_sort(RandomIt begin, RandomIt end) {
  if (begin &lt; end - 1) {
    const auto mid = begin + std::distance(begin, end) / 2;
    merge_sort(begin, mid);
    merge_sort(mid, end);
    sub_merge(begin, mid, end);
  }
}


My testing shows this to be correctly implemented, however I want to know if there is anywhere I could be more efficient. I also have no way to prove if my templates are used correctly. I also do not know which Iterator type is appropriate for this. STL uses RandomIterator so I went with that but I think InputIterator or possibly ForwardIterator would be suitable.
Naming

sub_merge is weird, as it doesn't match up at all with the meaning of the english word "submerge". I get its origin ("subroutine merge"), but why not simply call it merge instead?

Algorithm

This seems like a straightforward top-down implementation of mergesort. However, there are some issues:


Stability

sub_merge doesn't preserve the relative order of elements that compare equal. However, this can easily be fixed by changing the comparison operator in if(*left_iter &lt; *right_iter) from &lt; to &lt;=.
Allocations + copies

Since each sub_merge call creates its own scratch space, there are \$2n\$ allocations in total. This could be replaced by creating one scratch buffer at the highest level instead.

A benefit of doing so is the reduction in the number of necessary copies. Currently, sub_merge has to copy each element into the scratch space and then back into the original range. One of those copies could be skipped using a preallocated scratch buffer and alternating between it and the original range on different recursion levels, at the cost of one fixed copy when creating the scratch buffer.


Implementation


Why not use std::vector&lt;std::iterator_traits&lt;RandIter&gt;::value_type&gt; instead of manually managing the memory via those std::unique_ptrs?


Iterator categories

You are correct that a ForwardIterator would technically work for merge sort. However, using those would mean that you'd need 1.5 extra passes over the range for each midpoint calculation (1 pass for the std::distance call, and half a pass to find the mid iterator).

This wouldn't raise the runtime complexity into a worse category, but there are more efficient sorting strategies for those cases that don't require that many passes (especially since those passes usually aren't that cheap in data structures that only have ForwardIterators or BidirectionalIterators).

That's why RandomAccessIterators are preferred for merge sort.


  However, a lot of code would need to be changed for that to work, as ForwardIterators only need to support a small subset of the operations a RandomAccessIterator has to provide (i.e. they only have operators *, -&gt;, ++, == and !=, so no comparisons using &lt; or iteration using -).


So, why won't InputIterators work? Because merge sort requires multiple passes over the input/output range, and InputIterators don't guarantee that they can do so.

Improved version

With some improvements, the implementation could look something like this:

#include &lt;vector&gt;
#include &lt;type_traits&gt;

template&lt;typename Iter&gt;
constexpr bool is_forward_iterator_v = std::is_base_of_v&lt;std::forward_iterator_tag, typename std::iterator_traits&lt;Iter&gt;::iterator_category&gt;;

template&lt;typename ForwardIter&gt;
ForwardIter middle_iterator(ForwardIter first, ForwardIter last) {
    static_assert(is_forward_iterator_v&lt;ForwardIter&gt;, "middle_iterator requires at least a ForwardIterator to work properly");

    auto dist = std::distance(first, last);
    if(dist == 0) return first;

    return std::next(first, (dist + 1) / 2);
}

template&lt;typename InIter1, typename InIter2, typename OutIter&gt;
OutIter merge(InIter1 left, InIter1 left_end, InIter2 right, InIter2 right_end, OutIter out) {
    while(left != left_end &amp;&amp; right != right_end) {
        if(*left &lt;= *right) {
            *out++ = *left++;
        } else {
            *out++ = *right++;
        }
    }

    if(left != left_end) return std::copy(left, left_end, out);
    else return std::copy(right, right_end, out);
}

template&lt;typename Iter, typename Iter2&gt;
void merge_sort(Iter first, Iter last, Iter2 scratch, Iter2 scratch_end) {
    const auto mid = middle_iterator(first, last);
    if(mid != last) {
        const auto scratch_mid = middle_iterator(scratch, scratch_end);

        merge_sort(scratch, scratch_mid, first, mid);
        merge_sort(scratch_mid, scratch_end, mid, last);

        merge(scratch, scratch_mid, scratch_mid, scratch_end, first);
    }
}


template&lt;typename Iter&gt;
void merge_sort(Iter first, Iter last) {
    auto scratch_buffer = std::vector&lt;typename std::iterator_traits&lt;Iter&gt;::value_type&gt;(first, last);

    merge_sort(first, last, scratch_buffer.begin(), scratch_buffer.end());
}



  To Do:
  
  
  Better assert iterator requirements
  Add noexcept specifications where possible
  Maybe add support for move-only types?