Generic merge sort in C++ using a user-defined comparison function or the < operator by default I wanted to implement a generic merge sort algorithm using the same interface as std::sort(). The interface takes first and last iterators to a range of elements in any container. The user has the option to provide a custom function that compares two elements; if none is provided, the operator &lt; is used by default.

I handled the default case by creating a wrapper function that calls the real function using a lambda expression, but I'm wondering if there's a way to get rid of this second wrapper function.

Feedback on any aspect of the code is welcome.

template &lt;class RandomAccessIterator, class Compare&gt;
void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    size_t n = last - first;

    if (n &lt;= 1)
        return;

    size_t m = n / 2;

    mergesort(first, first + m, comp);
    mergesort(first + m, last, comp);

    std::vector&lt;RandomAccessIterator::value_type&gt; v(last - first);
    RandomAccessIterator itResult = v.begin();

    RandomAccessIterator itLower = first;
    RandomAccessIterator itUpper = first + m;

    while (itLower != first + m &amp;&amp; itUpper != last)
        *(itResult++) = comp(*itLower, *itUpper) ? *(itLower++) : *(itUpper++);

    if (itUpper == last)
        std::copy(itLower, first + m, itResult);
    else
        std::copy(itUpper, last, itResult);

    std::copy(v.begin(), v.end(), first);
}

template &lt;class RandomAccessIterator&gt;
void mergesort(RandomAccessIterator first, RandomAccessIterator last)
{
    mergesort(first, last, [](RandomAccessIterator::value_type a, RandomAccessIterator::value_type b) { return a &lt; b; });
}
Avoid a copy by passing by const reference.

[](RandomAccessIterator::value_type const&amp; a, RandomAccessIterator::value_type const&amp; b) { return a &lt; b; }
                                    ^^^^^^                                     ^^^^^^


Don't need an if statatement here:

if (itUpper == last)
    std::copy(itLower, first + m, itResult);
else
    std::copy(itUpper, last, itResult);


One of these ranges will be empty and just do nothing.

std::copy(itLower, first + m, itResult);
std::copy(itUpper, last, itResult);


To avoid a copy (which can be expensive on non POD types). Prefer to use move.

std::move(itLower, first + m, itResult);
std::move(itUpper, last, itResult);

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


You spend a lot of time creating the temporary array:

std::vector&lt;RandomAccessIterator::value_type&gt; v(last - first);


Basically this causes calls to new for every call to void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp). You can optimize this by allocating the temp space once in void mergesort(RandomAccessIterator first, RandomAccessIterator last) and pass the section of the temp array that recursive function can use. 

I know you are trying to be explicit with RandomAccessIterator. But it is more traditional to use single letter for template types. Also there is no compiler validation that your iterator is random accesses (so you are giving a false sense of security to your user).

C++20 should add Concepts (finally). Single letter template types will work well with this.

 template&lt;typename I&gt;
 requires RandomAccessIterator&lt;I&gt;
 void mergesort(I begin, I end){}


For C++ pre 20 You can write:

 template&lt;typename I&gt;
 // requires RandomAccessIterator&lt;I&gt;
 void mergesort(I begin, I end){}


Which provides the same information and when concepts are added you can just remove the comment.