7
\$\begingroup\$

A few month ago I wrote several basic sort algorithm for educational purposes as generic as possible in C++. In a few days time I want to present some of that stuff in my class but before that I thought I show my implementation to you and listen to your comments of what do you find confusing or very readable.

Mergesort

template <typename I>
    void merge(I first, I mid, I last) {
        while (first != mid && mid != last) {
            auto iter = mid;
            first = std::upper_bound(first, mid, *mid);
            mid = std::upper_bound(mid, last, *first);
            std::rotate(first, iter, mid);
        }
    }

What did I do here? Very simple; I want to avoid to allocate any new memory actively myself and try to write readable algorithm with as few loops as possible.

Obviously, I could not use the 'standard' way implementing merge not very readable. I also needed an in-place looking variant. So I started at looking what I actually do if I try to merge something in itself, what mergesort does in the end.

According to the STL documentation, std::upper_bound does the following:

Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The range [first, last) must be at least partially ordered, i.e. partitioned with respect to the expression !(value < element) or !comp(value, element). A fully-sorted range meets this criterion. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

I call this function twice, first to receive an Iterator of the first part of my array which is greater than the Item in the middle and then for my middle part which is greater than the Item behind my first Iterator of my array. Then I rotate those two "newly build" ranges.

According to the documentation, std::rotate does the following:

Performs a left rotation on a range of elements. Specifically, std::rotate swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first - 1 becomes the last element. A precondition of this function is that [first, n_first) and [n_first, last) are valid ranges.

template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

The precondition is always fulfilled because our ranges are within the array we want to merge stuff. This will be repeated as long first is not mid and mid is not equal to last, otherwise we merged our ranges.

What follows is simply the the algo for merge sort using the above implementation of merge:

template <typename I>
    void mergesort(I first, I last) {
        auto&& size = std::distance(first, last);
        if (size < 2) {
            return;
        }

        auto&& mid = first + size / 2 + size % 2;

        mergesort(first, mid);
        mergesort(mid, last);
        merge(first, mid, last);
    }
\$\endgroup\$
4
\$\begingroup\$

Well, it's a bit curious to indent after template<...>, but at least you are consistent there.

In merge() I would mark the only variable const.

In mergesort() I would make both variables const auto. There's no reason to make them references.

And I would change the initialization of mid so mutable forward-iterators are good enough. In addition, you only really need to refer to size once, though I expect any half-way useable compiler to optimize it appropriately.

const auto mid = std::next(first, (size + 1) / 2);

Be aware that if you have random-access-iterators and first / mid are generally only moved a relatively small amount in merge each iteration, std::find_if (O(n)) would beat std::upper_boud (O(log(n))). Not that it matters, your in-place-merge will be quadratic in that case anyway.

\$\endgroup\$
  • \$\begingroup\$ efficiency aka speed was not the goal but yes you are right about the quadratic nature. the indent after template<> is accidental ;) \$\endgroup\$ – ExOfDe Jul 22 '17 at 20:27

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.