6
\$\begingroup\$

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 < 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 <class RandomAccessIterator, class Compare>
void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    size_t n = last - first;

    if (n <= 1)
        return;

    size_t m = n / 2;

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

    std::vector<RandomAccessIterator::value_type> v(last - first);
    RandomAccessIterator itResult = v.begin();

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

    while (itLower != first + m && 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 <class RandomAccessIterator>
void mergesort(RandomAccessIterator first, RandomAccessIterator last)
{
    mergesort(first, last, [](RandomAccessIterator::value_type a, RandomAccessIterator::value_type b) { return a < b; });
}
\$\endgroup\$
8
\$\begingroup\$

Avoid a copy by passing by const reference.

[](RandomAccessIterator::value_type const& a, RandomAccessIterator::value_type const& b) { return a < 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<RandomAccessIterator::value_type> 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<typename I>
 requires RandomAccessIterator<I>
 void mergesort(I begin, I end){}

For C++ pre 20 You can write:

 template<typename I>
 // requires RandomAccessIterator<I>
 void mergesort(I begin, I end){}

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Will there be any predefined concepts in the library? Otherwise, people would need to reinvent them. \$\endgroup\$ – Incomputable Oct 27 '17 at 21:38
  • 1
    \$\begingroup\$ @Incomputable RandomAccessIterator and friends \$\endgroup\$ – Snowhawk Oct 27 '17 at 22:29
  • \$\begingroup\$ @Snowhawk, I guess I should’ve written Concepts, e.g. the new language feature. Sorry for not making it clear. At the moment, cppreference has only ranges prototype. \$\endgroup\$ – Incomputable Oct 27 '17 at 22:33
  • \$\begingroup\$ The Concepts TS does not specify any concept definitions. The goal for the Concepts TS was to ship a language extension, not provide library support. The committee didn't want to lock the language down to the current iteration of Concepts so they opted not to provide a concept definition library. Hopefully a library extension for Concept definitions is proposed/standardized once they address their immediate concerns. I just hope they can deliver on the abbreviated function template syntax. \$\endgroup\$ – Snowhawk Oct 28 '17 at 0:05
  • \$\begingroup\$ @Snowhawk, I've never heard of the latter term. This paper proposes removing them though. \$\endgroup\$ – Incomputable Oct 28 '17 at 11:09
5
\$\begingroup\$
template <class RandomAccessIterator>
void mergesort(RandomAccessIterator first, RandomAccessIterator last)
{
    mergesort(first, last, [](RandomAccessIterator::value_type a, RandomAccessIterator::value_type b) { return a < b; });
}

RandomAccessIterator::value_type prevents using this function for types such as simple C arrays, or even vectors if the vector uses a pointer as its iterator. Prefer typename std::iterator_traits<RandomAccessIterator>::value_type. I find that that's a mouthful, so I tend to use auto:

// since C++14, you can use `auto` as parameters to a lambda
[](auto const& a, auto const& b) { return a < b; }

Also, rather than comparing a < b, you should use std::less. Note that it is a functor, so you don't need to wrap it in a lambda:

mergesort(first, last, std::less<>{});

Note also that pointers need to be compared using std::less<T*>, so you should probably specify the value type (std::less<> compares using <):

mergesort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>{});

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

std::vector<RandomAccessIterator::value_type> v(last - first);
RandomAccessIterator itResult = v.begin();

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

while (itLower != first + m && 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);

If you are willing to use standard algorithms, as it seems, you can use std::inplace_merge:

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

std::inplace_merge(first, first + m, last, comp);

This will allocate memory each time you call it, so it's not as efficient as preallocating the buffer as Loki Astari suggested, but if you wanted to take Loki's suggestion, it may be desirable to factor out the merging into a function that behaves similarly.


You can reduce the requirements on your iterator. You declare that you want a RandomAccessIterator, but you really don't need that. Just use std::next and std::distance:

auto n = std::distance(first, last);

if (n <= 1)
    return;

auto middle = std::next(first, n / 2);

mergesort(first, middle, comp);
mergesort(middle, last, comp);

...

std::inplace_merge requires that its iterators are Bidirectional Iterators, so that could be your requirement. Do note that a different iterator class may have a different algorithmic complexity, so you'd have to evaluate if there was any change.

\$\endgroup\$
4
\$\begingroup\$

Just a small bit to add to the already great answers:

Correctness

RandomAccessIterator itResult = v.begin();

This line is not correct. An iterator over a vector might still be a random access iterator, but it very likely won't be of the same iterator type as the iterators passed in (e.g. iterators over a std::deque or a custom container).

If insisting on proper static typing, this could be remedied as follows:

std::vector<RandomAccessIterator::value_type>::iterator itResult = v.begin();
// maybe introduce a type alias?

However, there's a much simpler and more maintainable choice: Just let the type be deduced!

auto itResult = v.begin();

More material on the topic: CppCon 2014 Talk, GotW discussion, both by Herb Sutter.

\$\endgroup\$
0
\$\begingroup\$

Here's my updated version after implementing all the comments received. It runs around 50% slower than std::sort for 1,000,000 randomly-generated integers, which doesn't seem too bad for a simple algorithm (std::sort is a hybrid algorithm).

template <typename I, typename Compare>
void mergesortInternal(const I first, const I last, const Compare comp, 
    const typename std::vector<typename I::value_type>::iterator firstMerge)
{
    const size_t n = last - first;

    if (n <= 1)
        return;

    const size_t m = n / 2;

    mergesortInternal(first, first + m, comp, firstMerge);
    mergesortInternal(first + m, last, comp, firstMerge);

    auto merge = firstMerge;

    I lower = first;
    I upper = first + m;

    while (lower != first + m && upper != last)
        *(merge++) = comp(*lower, *upper) ? *(lower++) : *(upper++);

    std::move(lower, first + m, merge);
    std::move(upper, last, merge);

    std::move(firstMerge, firstMerge + n, first);
}

template <typename I, typename Compare = std::less<I::value_type>>
void mergesort(const I first, const I last, const Compare comp = Compare())
{
    std::vector<I::value_type> mergeSpace(last - first);

    mergesortInternal(first, last, comp, mergeSpace.begin());
}
\$\endgroup\$
  • \$\begingroup\$ A fairer comparison would be with std::stable_sort, as mergesort is a stable sorting algorithm \$\endgroup\$ – Justin Nov 1 '17 at 8:49
  • \$\begingroup\$ @Justin Then it's only ~ 25% slower :-) Thanks! \$\endgroup\$ – MGA Nov 1 '17 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.