Merge sort implementation using iterators

Question

Here is my first try to implement merge sort using iterators -

#include <algorithm>
#include <iterator>
#include <vector>
namespace base {
namespace merge {
 template <typename Iterator, typename Compare>
 void mergeBack(Iterator begin, Iterator mid, Iterator end, Compare comp)
 {
 typedef typename std::iterator_traits<Iterator>::value_type ElemType;
 std::vector<ElemType> left, right;
 left.reserve(mid - begin);
 right.reserve(end - mid);
 std::copy(begin, mid, std::back_inserter(left));
 std::copy(mid, end, std::back_inserter(right));
 size_t j = 0, k = 0;
 auto i = begin;
 for (; i != end && j < left.size() && k < right.size(); ++i) {
 *i = comp(left[j], right[k]) ? left[j++] : right[k++];
 }
 while (j < left.size()) {
 *(i++) = left[j++];
 }
 while (k < right.size()) {
 *(i++) = right[k++];
 }
 }
 template <typename Iterator, typename Compare = std::less<>>
 void sort(Iterator begin, Iterator end, Compare comp = Compare())
 {
 if (end - begin > 1) {
 const auto middle = (end - begin) / 2;
 merge::sort(begin, begin + middle, comp);
 merge::sort(begin + middle, end, comp);
 mergeBack(begin, begin + middle, end, comp);
 }
 }
}
}

I'm open to advice/suggestions about the implementation and would love to hear how I could make it better.

Answer 1

You should prefer to move values whenever possible.

std::move(begin, mid, std::back_inserter(left));
std::move(mid, end, std::back_inserter(right));
size_t j = 0, k = 0;
auto i = begin;
for (; i != end && j < left.size() && k < right.size(); ++i) {
 *i = std::move(comp(left[j], right[k]) ? left[j++] : right[k++]);
}
while (j < left.size()) {
 *(i++) = std::move(left[j++]);
}
while (k < right.size()) {
 *(i++) = std::move(right[k++]);
}

Every call of mergeBack will end up allocating 2 new buffers. You can avoid that by preallocating the secondary buffer and flip flopping between them but that is tricky to do in the recursive version. Which is why I prefer the iterative version that goes bottom up.

• Abhinav Gauniyal: if move isn't possible, will that operation fail to compile or switch to copy operation?
• Incomputable: Point of OP is correct, there should be some fallback mechanism. Solution can be std::move_if_noexcept()
• Incomputable: @AbhinavGauniyal, I think that if move isn't possible it will still compile. But if move can throw, the story changes a lot.
• coderodde: The bottom-up mergesort suffers from the following: suppose the length of the input range is \2ドル^k + 1\,ドル where \$k\$ is a positive integer. Now the very last merge will merge a run of length \2ドル^k\$ with a run of length of one element. (One single element will introduce an entire pass over the range.)
• ratchet freak: @coderodde you can adjust for that by letting the last range be larger by doing a extra merge if the last block size < 0.5*the current block size