Merge sort in C++ with iterators

Question

I implemented merge sort with C++ and would like to get some feedback.

#include <iterator>
#include <vector>
template<typename It>
std::vector<typename It::value_type> merge(const It begin, const It mid, const It end)
{
 std::vector<typename It::value_type> v;
 It it_l{ begin }, it_r{ mid };
 const It it_mid{ mid }, it_end{ end };
 
 while (it_l != it_mid && it_r != it_end)
 {
 v.push_back((*it_l <= *it_r) ? *it_l++ : *it_r++);
 } 
 v.insert(v.end(), it_l, it_mid); 
 v.insert(v.end(), it_r, it_end);
 return std::move(v);
}
template<typename It>
void merge_sort(It begin, It end)
{
 auto size = std::distance(begin, end);
 if (size < 2)
 return;
 
 auto mid = std::next(begin, size / 2);
 merge_sort(begin, mid);
 merge_sort(mid, end);
 auto &&v = merge(begin, mid, end);
 std::move(v.cbegin(), v.cend(), begin);
}

Usage:

std::vector<int> v{ 8, 4, 1, 9, 16, 3 };
merge_sort(v.begin(), v.end());

Is there anything I should avoid? Any mistakes in the algorithm or implementation? It should work with other containers (e.g. std::list) as well.

Answer 1

Very nice overall.
Don't see anything technically wrong.

I agree with @ratchet freak that your variable naming (and declaring multiple objects in one line) is a not great. I would prefer better names and one variable per line.

Things I would change for efficiency:

// You know how big this vector is going to get.
std::vector<typename It::value_type> v;
// So reserve the appropriate space:
v.reserve(std::distance(begin, end));

Also this is not what you want:

return std::move(v);
// jsut return the object
return v;

Otherwise you will screw up RVO done by the compiler and it will generate a copy rather than a move.

At the call site the value returned by a function is already an rvalue reference. So adding the move here does not change anything (it will still be moved).

But this is not going to move the values:

buffer.push_back((*left <= *right) ? *left++ : *right++);

Here you are only getting lvalues passed to push_back so you are copying the underlying elements. Why not try and get a move out of it?

buffer.push_back(std::move((*left <= *right) ? *left++ : *right++));

• Deduplicator: Actually, return std::move(loval_variable) is a pessimization, as it makes RVO impossible.

Answer 2

You may wish to allow the user to select his own Compare function instead of forcing operator<, and use std::less as default.

The naming in merge() is not great:

std::vector<typename It::value_type> buffer;
It left(begin);
It right(mid);
const It &left_end = mid; //by ref -> no copy
const It &right_end = end;
while (left != left_end && right != right_end)
{
 buffer.push_back((*left <= *right) ? *left++ : *right++);
} 
buffer.insert(v.end(), left, left_end); 
buffer.insert(v.end(), right, right_end);

The temporary buffer is repeatedly allocated and freed. Instead you can preallocate a buffer and pass it through as parameter.

Then during the merge you copy the values with push_back(); instead you can move from the selected iterator:

 buffer.push_back((*left <= *right) ? std::move(*left++) : std::move(*right++));

• ratchet freak: not really because that doesn't increment the iterator *left++ evaluates to *(left++) your solution inverts the priority nesting and increments the actual element

Answer 3

Please correct me if I'm wrong, but I believe this line is misleading:

std::move(v.cbegin(), v.cend(), begin);

std::move is called with const iterators, and therefore the program wouldn't benefit from move semantics: copy constructor will be called.

I think better would be to just use:

std::move(v.begin(), v.end(), begin);

Answer 4

Your function takes const It because it does not change the values of the variables named by the parameters; but it neglects to make the iterator refer to a const object, when the input is not modified by the function.

If the template auto-deduces a type which is a const_iterator of some kind, you are fine. But if you call it with something like v.begin(), v.end() where v was not const already, then you'll carry forward the non-const-ness of the iterators.

The top-level function that you actually call should declare local variables of the corresponding const_iterator and assign the parameters to those; basically, get the const on there as soon as possible without making it more complicated to write the template.