2
\$\begingroup\$

I wanted to implement merge sort in a generic way. I was not sure whether I should use the iterator or the container for the template type. I did not find a way to infer the container type using iterator_traits, so I decided to use the templated type for the container. Please let me know what you think!

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
void printArray(const T& a) {
    for (auto i: a) {
        cout << i << " ";
    }
    cout << endl;
}

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);
    auto firstIt = firstHalf.begin();
    auto secondIt = secondHalf.begin();
    T merged;
    while (firstIt != firstHalf.end() && secondIt != secondHalf.end()) {
        if (*firstIt < *secondIt) {
            merged.push_back(*firstIt);
            ++firstIt;
        } else {
            merged.push_back(*secondIt);
            ++secondIt;
        }
    }
    while(firstIt != firstHalf.end()) {
        merged.push_back(*firstIt);
        ++firstIt;
    }
    while(secondIt != secondHalf.end()) {
        merged.push_back(*secondIt);
        ++secondIt;
    }
    return merged;
}

int main() {
    vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
    printArray(mergeSort<vector<int>>(a.begin(), a.end()));
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Design

int main() {
    vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
    printArray(mergeSort<vector<int>>(a.begin(), a.end()));
    return 0;
}

My problem here is that you have to specify the type as part of the name of the function mergeSort<vector<int>>(). It would be much nicer if the compiler could work out the type for you, this would make modifying the code much easier in the long run.

In the above code if I change the type of a then I also need to change the type of mergeSort<vector<int>>(). In certain situations this could cause issues when coupled with auto-conversion.

I also dislike that you create a new container as a result of the sort. Why not sort in-place. A sort in-place can be used in conjunction with a copy to create a newly sorted container (but not the other way around).

Also your way of doing the sort allocates a lot of small arrays dynamically. This is very expensive. It would be better if you could allocate a temporary buffer that can be re-used by the sorting code.

The last thing in the design is that you use a single function to do all the work. In self documenting code it is much nicer to break your code into short self named (and thus explained) operations.

Code Review

Namespace using

Please don't do this:

using namespace std;

Thx! I never use "using namespace std;" for real code, this was just an exercise for myself, that's also why I wanted to implement merge for myself.

Thats not a good excuse. The trouble with doing it for small programs is that it becomes a reflex and you then accidentally do it all the time. Best not to form bad habits in the first place.

Also this code (if it had reviewed well) could have just been copied into a larger project and then polluted it.

Using const reference consistency.

Can you spot the issue here?

template<typename T>
void printArray(const T& a) {
    for (auto i: a) {
        cout << i << " ";
    }
    cout << endl;
}

What about i. Every iteration of the loop you are copying the value out of the container into the variable i. This is fine for POD or simple types. But what about complex types (or expensive to copy types).

    for (auto const& i: a) {
          //  ^^^^^^
        cout << i << " ";
    }

Assumptions Kill Generic abilities.

This assumes that the iterators are Random Access Iterators.

    auto n = end - begin;

You could use std::distance() this will allow you to find the count in the most efficient way no matter what the type of the iterator.

You only use Copy Semantics

Your merge moves the objects between containers using copy semantics.

            merged.push_back(*firstIt);

Since C++11 we have had move semantics. This (move) is never more expensive than a copy and usually much more efficient than a copy. None of your intermediate arrays are re-used. So there is no need to preserve the data in these intermediate containers. So you should be using move semantics when moving the objects internally.

Use standard algorithms were they are available.

    while(firstIt != firstHalf.end()) {
        merged.push_back(*firstIt);
        ++firstIt;
    }

This is obviously a copy.

    std::copy(firstIt, firstHalf.end(), std::back_inserter(merged));

Example

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

template<typename I, typename BI>
void mergeTogether(I begin, I mid, I end, BI beginBuffer)
{
    I  low = begin;
    I  hig = mid;
    BI buf = beginBuffer;
    while(low < mid && hig < end) {
        if (*low <= *hig) {
            std::iter_swap(low, buf);
            ++low;
        }
        else {
            std::iter_swap(hig, buf);
            ++hig;
        }
        ++buf;
    }
    std::move(low, mid, buf);
    std::move(hig, end, buf);

    std::size_t size = std::distance(begin, end);
    std::move(beginBuffer, std::next(beginBuffer, size), begin);
}

template<typename I, typename BI>
void mergeSortUsingBuffer(I begin, I end, BI beginBuffer)
{
    std::size_t size = std::distance(begin, end);
    if (size < 2) {
        return;
    }
    std::size_t split     = size/2;
    I           mid       = std::next(begin, split);
    BI          midBuffer = std::next(beginBuffer, split);

    mergeSortUsingBuffer(begin, mid, beginBuffer);
    mergeSortUsingBuffer(mid,   end, midBuffer);

    mergeTogether(begin, mid, end, beginBuffer);
}

template<typename I>
void mergeSort(I begin, I end)
{
    using       ValueType  = typename std::iterator_traits<I>::value_type;
    std::size_t size       = std::distance(begin, end);
    std::vector<ValueType>    buffer(size);

    mergeSortUsingBuffer(begin, end, std::begin(buffer));
}

int main()
{
    std::vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
    mergeSort(std::begin(a), std::end(a));
    std::copy(std::begin(a), std::end(a),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Good advice, just a line explaining how the move semantics should be done here would help this answer. \$\endgroup\$ – Felix Dombek Jan 6 '18 at 23:56
  • \$\begingroup\$ Thx for your review! > It would be much nicer if the compiler could work out the type for you, this would make modifying the code much easier in the long run. Sure, but how would you do it? If using the template type for iterators I couldn't figure out how to get the container type later in the function. \$\endgroup\$ – Nils Jan 7 '18 at 20:30
  • 1
    \$\begingroup\$ @Nils You would template on the type of the parameters to the function not the parent type. So make the template parameter about iterators not about containers. \$\endgroup\$ – Martin York Jan 8 '18 at 19:01
  • 1
    \$\begingroup\$ @Nils Added an example of how I would do based on all my comments. \$\endgroup\$ – Martin York Jan 8 '18 at 20:02
  • \$\begingroup\$ Ah ok in this case the buffer will be a vector, but the input could use a different container. Thx for sharing your implementation! \$\endgroup\$ – Nils Jan 9 '18 at 14:02
3
\$\begingroup\$

While your merge step in mergeSort works it should be put into its own function:

// Exercise: make `my_merge` even more generic
template <typename Iterator, typename OutputIterator>
void my_merge(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              OutputIterator out)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            *out++ = *first1++;
        } else {
            *out++ = *first2++;
        }
    }

    while(first1 != last1) {
        *out++ = *first1++;
    }
    while(first2 != last2) {
        *out++ = *first2++;
    }
}

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);

    T merged;

    my_merge(firstHalf.begin(), firstHalf.end(), 
             secondHalf.begin(), secondHalf.end(),
             std::back_inserter(merged));
    return merged;
}

Note that I had to call my_merge that way since std already contains std::merge, which we can use instead:

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(), 
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}

The merge and the parameters begin and end are good examples why using namespace std has to be handled with care. All those names are already in std. Use using namespace std only if you know the risks.

That being said, your generic variant will only work with random access iterators. If you want to make it more generic, you have to use std::distance and std::next instead of end - begin and begin + n/2:

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    const auto n = std::distance(begin, end);

    if (n < 2) {
        return T(begin, end);
    }
    const auto midpoint = std::next(begin, n / 2);

    const auto firstHalf  = mergeSort<T>(begin, midpoint);
    const auto secondHalf = mergeSort<T>(midpoint, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(), 
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}

Even if you don't want to use std::next re-use the midpoint.

\$\endgroup\$
  • \$\begingroup\$ Thx! I never use "using namespace std;" for real code, this was just an exercise for myself, that's also why I wanted to implement merge for myself. \$\endgroup\$ – Nils Jan 5 '18 at 22:37
  • 1
    \$\begingroup\$ @Nils I was almost asleep when I wrote that review. I forgot to say that you can provide your own merge version with a similar interface and thereby split mergeSort into two functions: one that splits, calls merge and calls itself recursively, and one that just merges. \$\endgroup\$ – Zeta Jan 6 '18 at 11:10
  • \$\begingroup\$ I agree with the split, makes it easier to read. \$\endgroup\$ – Nils Jan 7 '18 at 20:25

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.