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.

up vote 3 down vote accepted

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.

  • if move isn't possible, will that operation fail to compile or switch to copy operation? – Abhinav Gauniyal Feb 10 '17 at 16:01
  • Point of OP is correct, there should be some fallback mechanism. Solution can be std::move_if_noexcept() – Incomputable Feb 10 '17 at 16:57
  • @AbhinavGauniyal, I think that if move isn't possible it will still compile. But if move can throw, the story changes a lot. – Incomputable Feb 10 '17 at 17:40
  • 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.) – coderodde Feb 10 '17 at 17:59
  • @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 – ratchet freak Feb 10 '17 at 20:18

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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