9
\$\begingroup\$

I am trying to practice C++, so I decided to implement canonical algorithms in C++ as a way to learn best practices and idioms of the language.

I started with merge sort. How could I improve this routine?

I especially want to focus on ways of better using the features of C++. I've also included my tests, which I've written with the catch framework.

To run the test, just include the file available here https://github.com/catchorg/Catch2/releases/download/v2.13.8/catch.hpp

#define CATCH_CONFIG_MAIN
#include "catch.hpp"



std::vector<int> merge (std::vector<int> left, std::vector<int> right) {
    int num_terms = left.size() + right.size();
    std::vector<int> out = {};
    int l = 0, r = 0;
    for (int i = 0; i < num_terms; i++) {
        if (left[l] > right[r]) {
            out.push_back(right[r]);
            r++;
        } else {
            out.push_back(left[l]);
            l++;
        }

        if (l == left.size()) {
            while (r < right.size()) {
                out.push_back(right[r++]);
            }
            break;
        }

        if (r == right.size()) {
            while (l < left.size()) {
                out.push_back(left[l++]);
            }
            break;
        }
    }
    return out;
}


std::vector<int> merge_sort (std::vector<int> unsorted) {
    if (unsorted.size() <= 1) {
        return unsorted;
    }
    // recursively split vector into two vectors
    int middle = unsorted.size() / 2;
    std::vector<int> left = { unsorted.begin(), unsorted.begin() + middle };
    std::vector<int> right = { unsorted.begin() + middle, unsorted.end() };

    return merge(merge_sort(left), merge_sort(right));
}

TEST_CASE( "sorts lists of numbers", "[merge_sort]" ) {
    SECTION( "non-repeating") {
        std::vector<int> sorted = {1, 2, 3, 4, 5};
        std::vector<int> unsorted = {5, 2, 4, 3, 1 };
        REQUIRE(merge_sort(unsorted) == sorted);
    }

    SECTION("repeating") {
        std::vector<int> sorted = {1, 1, 2, 3, 4, 5, 6};
        std::vector<int> unsorted = {4, 1, 2, 1, 3, 6, 5};
        REQUIRE(merge_sort(unsorted) == sorted);
    }

    SECTION( "sorts lists with odd number of elements") {
        std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        std::vector<int> unsorted = {4, 7, 5, 6, 8, 2, 9, 1, 3 };
        REQUIRE(merge_sort(unsorted) == sorted);
    }

    SECTION("handles lists with two elements") {
        std::vector<int> sorted = {2, 8};
        std::vector<int> unsorted = {8, 2};
        REQUIRE(merge_sort(unsorted) == sorted);
    }

    SECTION("handles lists with one element") {
        std::vector<int> sorted = {8};
        std::vector<int> unsorted = {8};
        REQUIRE(merge_sort(unsorted) == sorted);
    }

    SECTION("handles empty lists") {
        std::vector<int> sorted = {};
        std::vector<int> unsorted = {};
        REQUIRE(merge_sort(unsorted) == sorted);
    }
}

TEST_CASE("merge merges sorted arrays", "[merge]") {
    SECTION("merges sorted vectors of even length") {
        std::vector<int> left = {1, 3, 5, 7};
        std::vector<int> right = {2, 4, 6, 8};
        std::vector<int> merged = {1, 2, 3, 4, 5, 6, 7, 8 };

        REQUIRE(merge(left, right) == merged);
    }

    SECTION("uneven length (l > r)") {
        std::vector<int> left = {1, 3, 5, 7};
        std::vector<int> right = {2, 4, 6 };
        std::vector<int> merged = {1, 2, 3, 4, 5, 6, 7 };

        REQUIRE(merge(left, right) == merged);
    }

    SECTION("uneven length (r > l)") {
        std::vector<int> left = {2, 5};
        std::vector<int> right = {1, 3, 4};
        std::vector<int> merged = {1, 2, 3, 4, 5};

        REQUIRE(merge(left, right) == merged);
    }

    SECTION("duplicate elements") {
        std::vector<int> left = {2, 2, 5};
        std::vector<int> right = {1, 3, 3, 4};
        std::vector<int> merged = {1, 2, 2, 3, 3, 4, 5};

        REQUIRE(merge(left, right) == merged);
    }

    SECTION("one half emptying first") {
        std::vector<int> left = {4, 6};
        std::vector<int> right = {1, 3 };
        std::vector<int> merged = {1, 3, 4, 6};

        REQUIRE(merge(left, right) == merged);
    }

    SECTION("input of two elements") {
        std::vector<int> left = {8};
        std::vector<int> right = {2};
        std::vector<int> merged = {2, 8};

        REQUIRE(merge(left, right) == merged);
    }
}
\$\endgroup\$
0

3 Answers 3

Reset to default
14
\$\begingroup\$

Avoid unnecessary copies

Your algorithm passes vectors solely by value. That means a copy is made each time. This can be very expensive for large arrays. Consider passing vectors that are not going to modified as const references:

std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
    ...
}

std::vector<int> merge_sort(const std::vector<int>& unsorted) {
    ...
}

Note however that inside merge_sort(), you are splitting the unsorted input into left and right vectors. That is again making a copy, but what you actually only need is a view of the left and right part of the input vector. Pre C++20, you would do that by passing begin and end iterators. That means std::merge() would need to take four parameters. However, since C++20 you could use std::span or std::ranges::subrange instead.

But another issue is that merge() is returning the result by value. Perhaps you do want an out-of-place merge sort, so merge_sort() itself should return by value, but the drawback of this is that still a lot of temporary vectors are going to be allocated and destroyed before you get the final output. The conclusion you could draw from this is that you should consider implementing an in-place merge sort instead, and let the caller create a copy if so desired.

Use std::size_t instead of int for sizes and indices

Consider trying to sort a vector with \$2^{31}\$ or more entries on a typical 64-bit machine. This will fail because you are storing sizes and indices of vectors in int variables. You should use std::size_t instead, as that is guaranteed to be able to hold any valid index or size of things that can be stored in memory.

Consider making this a template

A big problem is that your merge_sort() function only works for std::vector<int>. What if you want to sort a std::vector<float>? Or what if it's not a vector but a C array or a std::deque<int>? Turning your functions into templates allows them to work on a wider variety of types, without you having to write more code.

The easiest change to make to your code is to make it sort vectors of arbitrary types:

template<typename T>
std::vector<T> merge_sort(const std::vector<T>& unsorted) {
    ...
}

And of course make sure every occurence of std::vector<int> in the body of your functions is replaced with std::vector<T>. But ideally, you could make it work for arbitrary containers:

template<typename Container>
Container merge_sort(const Container& unsorted) {
    ...
}

You replace every occurence of std::vector<int> with Container, and then it would work with things that work very much like a std::vector, like std::deque, but it wouldn't work with std::list, std::array or C arrays, since you require that the Container type has member functions like size(), and that it can be randomly indexed using []. You can make it work for more types of containers by using std::size() and iterator operations like std::advance().

Going further

Consider that you might want to sort an array not based on the natural ordering of their elements (usually defined by the comparison operators like < and >), but based on some other property. For example, maybe you want to sort ints based on their absolute value, or on their value modulo 42. For this reason, the standard library's sorting functions like std::sort() and std::ranges::sort() take an optional comparison function as a parameter.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ int is guaranteed to be at least 16 bits wide. That means on some systems, trying to sort a list of length least 2<sup>15</sup> can break the algorithm. Conversely, int could be 64 bits wide, which means your claim of "This will fail" won't hold. \$\endgroup\$ Commented Mar 7, 2022 at 5:37
3
\$\begingroup\$

The worst issue is that you copy the arrays around.

std::vector<int> merge (std::vector<int> left, std::vector<int> right) {

Here you are passing a copy of the left and right to be merged.

The second issue is the number of times you allocate temporary objects.

    std::vector<int> left = { unsorted.begin(), unsorted.begin() + middle };
    std::vector<int> right = { unsorted.begin() + middle, unsorted.end() };

This is done every time you split the container. In addition to having to lots of vector creation operations, you actually create a peak need for twice the original vectors memory in temporary memory. You can reduce this requirement.

You can solve both these problems by using a top level wrapper that does the allocation once and allows you to reuse the allocated space in all the subsequent functions. Allow you're implementation to use iterators as the algorithm interface to abstract you away from the specific type.

// Sort in place.
// If you don't want to sort in place, then manually create a copy
// and sort the copy in place.
template<typename C>
void merge_sort(C& dataToSort)
{
    // Note: use `std::size()/std::begin()/std::end()
    //       This allows you to use containers that don't have methods.
    //       Like a normal C-Array.
    using D = typename C::value_type;   // Type of data being sorted.
    std::vector<D>   tempBuffer(std::size(dataToSort));

    merge_sort_do(std::begin(dataToSort), std::end(dataToSort),
                  std::begin(tempBuffer), std::end(tempBuffer));
}

template<typename I, typename VI>
void merge_sort_do(I begin, I end, VI, tBegin, VI tEnd)
{
    // Now write the code you would have written.
    // But no need to allocate temporary data just use
    // the temporary buffer provided. It can also be split
    // just like the data container.

    // Use tBegin/tEnd as we know this is a random access
    // container, and thus has a very efficient distance implementation.
    std::size_t size = std::distance(tBegin, tEnd)

    if (size <= 1) {
        return;
    }

    // recursively split vector into two vectors
    I middle = begin;
    std::advance(middle, size / 2);
    VI tMiddle = tBegin;
    std::advance(tMiddle, size / 2);


    merge_sort_do(begin, middle, tBegin, tMiddle),
    merge_sort_do(middle, end,   tMiddle, tEnd);
    merge(begin, middle, end, tBegin, tMiddle, tEnd);
}

template<typename I, typename VI>
void merge(I begin, I middle, I end, VI tBegin, VI tMiddle, tEnd)
{
}

So you wrote your function with integers in mind. And integers are easy to copy. There is no more efficient way to copy integers, as they just a single chunk of memory.

But not all types are effecient to copy.When possible you should use move semantics. std::move().

So lines like this:

            out.push_back(right[r]);

Should be written line:

            out.push_back(std::move(right[r]));

While loops like this:

            while (l < left.size()) {
                out.push_back(left[l++]);
            }

Should be replaced by standard methods:

           std::move(std::begin(left) + l, std::end(left),
                     std::back_inserter(out));
\$\endgroup\$
-1
\$\begingroup\$

Sliepen said the main points. I'll try to add my two cents.

Notice you don't need to specify = {} in std::vector<int> out = {};. Writing std::vector<int> out; would be enough and it would call the default constructor.

If you make the functions template as Slipen suggested, you can use concepts as the

\$\endgroup\$
1
  • 10
    \$\begingroup\$ "you can use concepts as the"...? \$\endgroup\$ Commented Mar 7, 2022 at 5:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.