Merge Sort implemented using iterators

Question

#include <iterator>
#include <memory>
#include <algorithm>

template<typename RandomIt>
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<typename std::iterator_traits<RandomIt>::value_type[]>(left_size);
  auto right = std::make_unique<typename std::iterator_traits<RandomIt>::value_type[]>(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 < left_end && right_iter < right_end) {
    if (*left_iter < *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<typename RandomIt>
void merge_sort(RandomIt begin, RandomIt end) {
  if (begin < 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.

Answer 1

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 < *right_iter) from < to <=.

• 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<std::iterator_traits<RandIter>::value_type> 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 *, ->, ++, == and !=, so no comparisons using < 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 <vector>
#include <type_traits>

template<typename Iter>
constexpr bool is_forward_iterator_v = std::is_base_of_v<std::forward_iterator_tag, typename std::iterator_traits<Iter>::iterator_category>;

template<typename ForwardIter>
ForwardIter middle_iterator(ForwardIter first, ForwardIter last) {
    static_assert(is_forward_iterator_v<ForwardIter>, "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<typename InIter1, typename InIter2, typename OutIter>
OutIter merge(InIter1 left, InIter1 left_end, InIter2 right, InIter2 right_end, OutIter out) {
    while(left != left_end && right != right_end) {
        if(*left <= *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<typename Iter, typename Iter2>
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<typename Iter>
void merge_sort(Iter first, Iter last) {
    auto scratch_buffer = std::vector<typename std::iterator_traits<Iter>::value_type>(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?

Answer 2

Well, interesting.

1. There's a bug in merge_sort(): Subtracting 1 from end, without knowing whether the range is empty, is Undefined Behavior. Subtract the iterators and compare the difference instead. While you are at it, use std::distance for that.

2. There's no need to move the second half out of the way in sub_merge(): You are merging from the front, and the first half fits in the first half of the range.

3. Allocating memory is expensive. Consider whether you can't do one allocation in the public function, and pass it through to the helpers as needed.

4. Also consider whether you wouldn't prefer your ordering stable. It doesn't cost anything but being careful with the merge. Currently, you prefer the second range where you should prefer the first.

5. Use prefix operators over postfix operators, unless you really need the copy of the old value. The clarity of intent and occasional increased efficiency shouldn't be rejected.

Answer 3

This assumes that the type being copied has a default constructor.

  auto left = std::make_unique<typename std::iterator_traits<RandomIt>::value_type[]>(left_size);
  auto right = std::make_unique<typename std::iterator_traits<RandomIt>::value_type[]>(right_size);

If you use std::vector you can use the constructor that takes iterators and create and copy the elements in one go:

  // Replace all this with:
  auto left = std::make_unique<typename std::iterator_traits<RandomIt>::value_type[]>(left_size);
  auto right = std::make_unique<typename std::iterator_traits<RandomIt>::value_type[]>(right_size);

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

 // Replace all the above with.
 using ValueType = std::iterator_traits<RandomIt>::value_type;
 std::vector<ValueType>   leftSide(begin, mid);
 std::vector<ValueType>   rightSide(mid,  end);

But we are still using a copy.
So lets improve the efficiency with moving the objects.

 using ValueType = std::iterator_traits<RandomIt>::value_type;
 std::vector<ValueType>   leftSide(std::make_move_iterator(begin), std::make_move_iterator(mid));
 std::vector<ValueType>   rightSide(std::make_move_iterator(mid),  std::make_move_iterator(end));

We can also improve the merge part by again using move:

       *arr_iter = std::move(*left_iter);

But lets reduce the whole expression to make it easier to read:

       ValueType&  lObject = *left_iter;
       ValueType&  rObject = *right_iter;
       auto&       mIter   = (lObject < rObject) ? left_iter : right_iter;
       ValueType&  mObject = *mIter++;
       *arr_iter = std::move(mObject);

At the end lets make sure we move rather than copy

  // This can be replaced with:
  std::copy(right_iter, right_end, arr_iter);
  std::copy(left_iter, left_end, arr_iter);


  // Move version of copy; called move (no need for move iterators):
  std::move(right_iter, right_end, arr_iter);
  std::move(left_iter, left_end, arr_iter);

You are making an assumption here (that begin != end)

  if (begin < end - 1) {

Easier to use:

  if (std::distance(begin, end) > 1) {

Note:

Your types don't need to be move able to use this. If there is no move semantics associated with the object then copy will be used as a backup automatically. But this way if they are moveable then you will use the move operation,