Move friendly merge sort - follow-up This is a follow up to this question. I'm only interested to see if this is implemented correctly for move-only types.

#include &lt;vector&gt;
#include &lt;iterator&gt;
#include &lt;algorithm&gt;
#include &lt;utility&gt;

namespace sorting {
  namespace detail {
    template&lt;typename RandomIt&gt;
    RandomIt middle_iterator(RandomIt begin, RandomIt end) {
      return std::next(begin, (end - begin) / 2);
    }

    template&lt;typename RandomIt1, typename RandomIt2, typename OutIt&gt;
    OutIt merge(RandomIt1 left, RandomIt1 left_end, RandomIt2 right, RandomIt2 right_end, OutIt out) {
      while(left &lt; left_end &amp;&amp; right &lt; right_end) {
        if (*left &lt; *right) {
          *out++ = std::move(*left++);
        } else {
          *out++ = std::move(*right++);
        }
      }

      std::move(left, left_end, out);
      std::move(right, right_end, out);
      return out;
    }
  }

  template&lt;typename RandomIt1, typename RandomIt2&gt;
  void merge_sort(RandomIt1 begin, RandomIt2 end, RandomIt2 scratch_begin, RandomIt2 scratch_end) {
    if (end - begin &gt; 1) {
      const auto mid = detail::middle_iterator(begin, end);
      const auto scratch_mid = detail::middle_iterator(scratch_begin, scratch_end);
      merge_sort(scratch_begin, scratch_mid, begin, mid);
      merge_sort(scratch_mid, scratch_end, mid, end);
      detail::merge(scratch_begin, scratch_mid, scratch_mid, scratch_end, begin);
    }
  }

  template&lt;typename RandomIt&gt;
  void merge_sort(RandomIt begin, RandomIt end) {
    using value_type = typename std::iterator_traits&lt;RandomIt&gt;::value_type;
    auto scratch_buffer = std::vector&lt;value_type&gt;(std::make_move_iterator(begin), std::make_move_iterator(end));
    merge_sort(begin, end, scratch_buffer.begin(), scratch_buffer.end());
  }
}
It certainly looks clean and well-written.
Just one thing, I really hate horizontal scrolling. I acknowlege this site is very restrictive there though.


Make sure your use of move-semantics is type-appropriate:


Move if it's a move-only type.
Move if moveing is noexcept.
Otherwise, don't move it.


The standard-library already has to do that in many places, and thankfully it is available to the public as std::move_if_noexcept() analogous to std::move.

I suggest adding your own helper which does that for iterators.
You know, it's itching in my fingers to modify merge() to use the conditional operator. Especially after applying the above point, which makes the common part even bigger.
One of the advantages moveing is that it allows for guaranteed success in more cases. Yes, writing flexible and comprehensive noexcept-specifications can be a pain, but your callers will thank you.

Without doing that work, a good part of the advantage of the two-range version is lost.
I would suggest renaming your iterator-ranges source and target respectively, neither is properly scratch. Also, I would use the more common temp as a name in merge_sort(begin, end).
Are you aware of the sordid tale that is std::vector&lt;bool&gt;?
I'm not saying it won't work in this case, though slowly.
You do know that C++17 has class template argument deduction?
It's nice to see that you only use &lt; for comparisons, just like the standard-library. That should enable you to easily modify your code to allow for a custom comparison-object.
But there is a problem in how you do the comparisons, as your merge() is needlessly not stable: If both are equal, you should take from the left range instead.
Consider asserting that the two iterator-types fit together in the function, or testing it for SFINAE outside.