Merge sort implementation using iterators

Question 1

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.

Question 2

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.

Question 3

if move isn't possible, will that operation fail to compile or switch to copy operation?

Question 4

Point of OP is correct, there should be some fallback mechanism. Solution can bestd::move_if_noexcept()

Question 5

@AbhinavGauniyal, I think that if move isn't possible it will still compile. But if move can throw, the story changes a lot.

Question 6

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.)

Question 7

@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 13k23 silver badges46 bronze badges · Accepted Answer · 2017-02-10 14:25:30Z

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?
Point of OP is correct, there should be some fallback mechanism. Solution can bestd::move_if_noexcept()
@AbhinavGauniyal, I think that if move isn't possible it will still compile. But if move can throw, the story changes a lot.
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 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

Movatterモバイル変換

Stack Exchange Network

Merge sort implementation using iterators

1 Answer1

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS