8
\$\begingroup\$

I'm trying to learn proper C++ and algorithms at the same time.

I particularly feel weird about my iterators usage in merge function. Is this a good way to handle it? I've modeled the signature after the STL std::merge method in <algorithm>.

I've tagged it as C++11 as well, because ideally I would've liked to make use of the new features like move semantics and rvalues, but it seems that I'm misunderstanding how they're supposed to work - no matter where I try to use them, my running time actually drops...

#include <vector>

typedef std::vector<int>::iterator vec_it;
void merge(vec_it left, vec_it left_end, vec_it right, vec_it right_end, vec_it numbers)
{
    while (left != left_end) {
        if (*left < *right || right == right_end) {
            *numbers = *left;
            ++left;
        } else {
            *numbers = *right;
            ++right;
        }

        ++numbers;
    }

    while (right != right_end) {
        *numbers = *right;
        ++right;
        ++numbers;
    }
}

void merge_sort(std::vector<int>& numbers)
{
    if (numbers.size() <= 1) {
        return;
    }

    std::vector<int>::size_type middle = numbers.size() / 2;
    std::vector<int> left(numbers.begin(), numbers.begin() + middle);
    std::vector<int> right(numbers.begin() + middle, numbers.end());

    merge_sort(left);
    merge_sort(right);

    merge(left.begin(), left.end(), right.begin(), right.end(), numbers.begin());
}
\$\endgroup\$
  • 1
    \$\begingroup\$ One thing I noticed. You're treating the collection as one and breaking it down to it's smallest parts then doing the merge. If you treat the collection as elements and start merging from there you'll find a large increase in efficiency. \$\endgroup\$ – tinstaafl May 11 '14 at 14:54
  • \$\begingroup\$ @tinstaafl could you please elaborate? Do you mean I should work with indices of the container, rather than container itself? But wouldn't that invalidate iterators during the merge? \$\endgroup\$ – Inoryy May 11 '14 at 15:04
  • 1
    \$\begingroup\$ @Inoryy: I think what tinstaffl is saying is that you are building intermediate vectors at each iteration. Then pulling them back into the original. Thus using O(n^2) space. If you did this in-place in the original array it is just O(n) space. \$\endgroup\$ – Martin York May 11 '14 at 18:09
  • \$\begingroup\$ If you'd like further review, please post a new follow-up question. We don't prefer to have extended reviews of multiple code blocks in one question as that will complicate the review process. \$\endgroup\$ – Jamal May 14 '14 at 19:31
13
\$\begingroup\$

Looks good.

Couple of things I would do differently (not that your way is wrong).

Rather than pass references to the containers around I would pass iterators into the containers. This allows your sort algorithm to be container agnostic:

void merge_sort(std::vector<int>& numbers)
{}

// My version looks like this

template<typename I>                 // Notice the template
void merge_sort(I begin, I end)      // Just means I don't care what type
{}                                   // of iterator is used.

Same applies to merge().

Rather than creating sub arrays in merge_sort() I would do it inside merge(). With your current implementation you have a space complexity of \$O(N^2)\$. If you do it inside the merge you just need to allocate enough space to merge the current two ranges which is at most \$O(2N)\$ => \$O(N)\$.

Where you have:

std::vector<int>::size_type middle = numbers.size() / 2;
std::vector<int> left(numbers.begin(), numbers.begin() + middle);
std::vector<int> right(numbers.begin() + middle, numbers.end());

merge_sort(left);
merge_sort(right);

// My version looks like this:

std::size_t mid      = length/2;
I           midPoint = std::next(begin, mid);

// Merge in place.
mergeSort(begin, midPoint);
mergeSort(midPoint, end);

I could not work out how to merge without using a temporary (and I don;t have my copy of Knuth here). So my version of merge() merges the two sorted sub vectors into a temporary then copies back over the original.

Looking at your merge code it's slightly hard to follow (but I groked it). I personally prefer a simpler version.

// In this loop:
//    l:     current position in left  sub-array
//    r:     current position in right sub-array
//    i:     current position into merged array.
//    Note because we are merging in-place.
//    begin/midPoint/end are iterators to the input arrays that
//    split it into two parts.
while(l < midPoint && r < end)
{
    if (*l < *r)
    {    *i = *l;
         ++i;
         ++l;
    }
    else
    {    *i = *r;
         ++i;
         ++r;
    }
}
// One of the ranges is empty at this point.
// So only one of the loops will execute.
while(l < midPoint)
{   *i  = *l;
    ++i;
    ++l;
}
while(r < end)
{   *i  = *r;
    ++i;
    ++r;
}

A slight variation on this that I use; Where you use if () {} else {} I prefer to use the Condition Operator => Test ? <TrueWork> : <FalseWork>. I also have done this a few times and can safely compress ++ operations onto the same lines (Note I don't compress all of them; this is just personal preferences as I think it makes it easier to read this way). Which leaves me with:

while(l < midPoint && r < end)
{
    *i = std::move((*l < *r) ? *l++ : *r++);
    ++i;
}
while(l < midPoint)
{   *i  = std::move(*l++);
    ++i;
}
while(r < end)
{   *i  = std::move(*r++);
    ++i;
}

Notice: I use std::move() here. This is because my sort works on generic containers (not just integer containers). So I may be sorting an array of strings.

Final result is:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

template<typename I>
void doMerge(I begin, I midPoint, I end)
{
    typename std::vector<typename std::iterator_traits<I>::value_type> TmpVec;

    TmpVec  tmp(std::make_move_iterator(begin), std::make_move_iterator(end));

    TmpVec::iterator   beginAlt   = std::begin(tmp);
    TmpVec::iterator   endAlt     = std::end(tmp);
    TmpVec::iterator   midAlt     = std::next(beginAlt, std::distance(begin, midPoint));


    TmpVec::iterator   l   = beginAlt
    TmpVec::iterator   r   = midAlt;
    I                  i   = begin;

    while(l < midAlt && r < endAlt)
    {
        *i = std::move((*l < *r) ? *l++ : *r++);
        ++i;
    }
    while(l < midAlt)
    {   *i  = std::move(*l++);
        ++i;
    }
    while(r < endAlt)
    {   *i  = std::move(*r++);
        ++i;
    }
}
template<typename I>
void mergeSort(I begin, I end)
{
    std::size_t length  = std::distance(begin, end);
    if (length <= 1)
    {   return;
    }

    std::size_t mid      = length/2;
    I           midPoint = std::next(begin, mid);

    mergeSort(begin, midPoint);
    mergeSort(midPoint, end);

    doMerge(begin, midPoint, end);
}


int main()
{
    std::vector<int>    data  {{ 5,12,45,2,67,8}};
    mergeSort(std::begin(data), std::end(data));

    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";
}
\$\endgroup\$
  • \$\begingroup\$ tmp(std::distance(begin, end)) will value-initialize. OP suggested in the updated question to copy to tmp in the ctor and then merging back to begin. What do you think? \$\endgroup\$ – dyp May 14 '14 at 23:04
  • \$\begingroup\$ @dyp: Good idea. Altered final example. Took a few tweaks to make sure we always use move semantics. \$\endgroup\$ – Martin York May 14 '14 at 23:47
8
\$\begingroup\$

I could not work out how to merge without using a temporary

There are two distinct flavours of merge. One is a generic merge of two totally unrelated ranges, which cannot possibly happen inplace, with the signature

template <typename I>
void merge(I first1, I last1, I first2, I last2, I target);

The second one, actually employed in the merge sort, assumes that the range are adjacent, hence less parameters:

template <typename I>
void merge(I first, I mid, I last);

This one can be done inplace, while maintaining stability. The algorithm is so beautiful, I can't help but spell it out here. It is also very instructive. Notice the recursive nature of the merge phase; that's what makes inplace possible.

// Preconditions: is_sorted(first, mid) && is_sorted(mid, last)
template <typename I>
void merge(I first, I mid, I last)
{
    if (first == mid || mid == last) return;
    I lm = midpoint(first, mid);
    I rm = lower_bound(mid, last, *lm);
    mid = rotate(lm, mid, rm);
    merge(l, lm, mid);
    merge(mid, rm, last);
}

midpoint is very straightforward; lower_bound is a variation on a binary search theme. rotate is the most saddle for you have to understand what does it return, and why. Of course there's huge room for optimization.

\$\endgroup\$
1
\$\begingroup\$

There is a suspicious piece in your merge function:

    if (*left < *right || right == right_end) ....

You're testing the value at the right iterator before testing if the iterator is valid! Should be:

    if (right == right_end || *left < *right) ....

Additionally you compare items to be merged with a 'less-than' instead of 'less-or-equal' operator. That causes taking equal items from the right part first, which violates the usual stability of the merge-sort.

The whole merge routine more compact:

{
    while (left != left_end && right != right_end) {
        if (*left <= *right) {
            *numbers ++ = *left ++;
        } else {
            *numbers ++ = *right ++;
        }
    }

    while (left != left_end)
        *numbers ++ = *left ++;
    while (right != right_end)
        *numbers ++ = *right ++;
}
\$\endgroup\$

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.