2
\$\begingroup\$

Any suggestions on how to improve this code (other than arbitrary call-stack depth)?

#include <iostream>
#include <vector>

template <typename T>
void merge(const std::vector<T>& left, const std::vector<T>& right, std::vector<T>& merged)
{
    auto i = left.begin();
    auto j = right.begin();
    auto k = merged.begin();

    while (i != left.end() && j != right.end())
    {
        *k = (*i < *j) ? *i : *j;
        if (*i < *j) ++i;
        else ++j;
        ++k;
    }
    while (j != right.end())
    {
        *k = *j; ++k; ++j;
    }
    while (i != left.end())
    {
        *k = *i; ++k; ++i;
    }
}

template <typename T>
void merge_sort(std::vector<T>& A)
{
    if (A.size() <= 1) return;
    size_t mid = A.size() / 2;
    std::vector<T> left(A.begin(), A.begin() + mid);
    std::vector<T> right(A.begin() + mid, A.end());
    merge_sort(left);
    merge_sort(right);
    merge(left,right, A);
}

int main()
{
    std::vector<int> input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector<int> sorted = {1, 2, 3, 7, 9, 10, 11, 12, 14, 14, 15, 16, 17, 19};
    bool success = true;
    merge_sort(input);
    for (size_t i = 0; i < input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout << "Merge sort " << (success ? "passed\n" : "failed\n");
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

There is more efficient and idiomatic ways of implementing merge sort, yet I will assume your style. I have embedded my comments directly in your code whenever I have something to say:

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

template <typename T>
void merge(const std::vector<T>& left_vector,
           const std::vector<T>& right_vector,
           std::vector<T>& merged_vector)
{
    /*
    auto i = left.begin();
    auto j = right.begin();
    auto k = merged.begin();
    */
    // Better names + names for end iterators in order not to call end() on each
    // iteration:
    auto left      = left_vector.begin();
    auto right     = right_vector.begin();
    auto merged    = merged_vector.begin();
    auto left_end  = left_vector.end();
    auto right_end = right_vector.end();

    /*
    while (i != left.end() && j != right.end())
    {
        *k = (*i < *j) ? *i : *j;
        if (*i < *j) ++i;
        else ++j;
        ++k;
    }*/
    // Would be more efficient since you compare only once per iteration:
    while (left != left_end && right != right_end)
    {
        if (*right < *left)
        {
            *merged = *right;
            ++right;
        }
        else
        {
            *merged = *left;
            ++left;
        }

        ++merged;
    }

    /*
    while (j != right.end())
    {
        *k = *j; ++k; ++j;
    }
    while (i != left.end())
    {
        *k = *i; ++k; ++i;
    }*/
    // Here you could use std::copy. Only one of these two calls will have an
    // effect, since either left < left_end or right < right_end:
    std::copy(left, left_end, merged);
    std::copy(right, right_end, merged);
}

template <typename T>
void merge_sort(std::vector<T>& A)
{
    if (A.size() <= 1) return;
    size_t mid = A.size() / 2;
    std::vector<T> left(A.begin(), A.begin() + mid);
    std::vector<T> right(A.begin() + mid, A.end());
    merge_sort(left);
    merge_sort(right);
    merge(left,right, A);
}

int main()
{
    std::vector<int> input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector<int> sorted = {1, 2, 3, 7, 9, 10, 11, 12, 14, 14, 15, 16, 17, 19};
    /*
    merge_sort(input);
    bool success = true;
    merge_sort(input);
    for (size_t i = 0; i < input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout << "Merge sort " << (success ? "passed\n" : "failed\n");
     */
    // You can write better:
    merge_sort(input);
    std::cout << "Merge sort passed: "
              << std::boolalpha
              << std::equal(input.begin(),
                            input.end(),
                            sorted.begin(),
                            sorted.end())
              << std::endl;
}

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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