3
\$\begingroup\$

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion. Just one question which is better *k++ = *i++; or, *k = *i; ++k; ++i;.

/*
 *    Merge Sort
 */

#include <iostream>
#include <vector>

void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);

int main()
{
    std::ios_base::sync_with_stdio(false);

    std::vector<int> v;

    int temp = 0;
    while (std::cin >> temp) {
        v.push_back(temp);
    }

    // Sort
    mergeSort(v, v.begin(), v.end() - 1);
    // Print the vector after sorting.
    print(v);

    return 0;
}

void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
    // Base case: if (p >= r) then return
    if (p < r) {
        auto q = p + (r - p) / 2;

        mergeSort(v, p, q);
        mergeSort(v, q+1, r);
        merge(v, p, q, r);
    }
}

void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
    std::vector<int>::size_type leftVectorSize = q - p + 1;
    std::vector<int>::size_type rightVectorSize = r - q;

    std::vector<int> vLeft(leftVectorSize);
    std::vector<int> vRight(rightVectorSize);

    // Copy elements p to q
    auto it = p;
    for (auto &i : vLeft) {
        i = *it++;
    }

    // Copy elements q + 1 to r
    for (auto &i : vRight) {
        i = *it++;
    }

    auto i = vLeft.cbegin(), j = vRight.cbegin();
    auto k = p;

    // Compare and merge
    while (i != vLeft.end() && j != vRight.end()) {
        if (*i <= *j) {
            *k++ = *i++;
        } else {
            *k++ = *j++;
        }
    }

    // Copy rest of the elements if any
    while (i != vLeft.end()) {
        *k++ = *i++;
    }

    // Copy rest of the elements if any
    while (j != vRight.end()) {
        *k++ = *j++;
    }
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << "\n";
    }
}
\$\endgroup\$
4
\$\begingroup\$

Advice 1

mergeSort(v, v.begin(), v.end() - 1);

So your implementation requires the actual vector + two iterators; this is an anti-pattern, you should strive for the following API:

mergeSort(v.begin(), v.end());

Note v.end() instead of v.end() - 1, since end() points to the one element past the last element; this is the STL approach.

Advice 2

Same applies to the merge.

Summa summarum

If you want to improve your coding, you could start by investigating the following:

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

void mergeSort(std::vector<int>::iterator begin,
               std::vector<int>::iterator end);

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end);

void print(const std::vector<int> &v);

int main()
{
    std::ios_base::sync_with_stdio(false);

    std::vector<int> v;

    int temp = 0;
    while (std::cin >> temp) {
        v.push_back(temp);
    }

    // Sort
    mergeSort(v.begin(), v.end());
    // Print the vector after sorting.
    print(v);

    return 0;
}

void mergeSort(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);

    if (distance < 2) {
        return;
    }

    auto middle = begin;
    std::advance(middle, distance / 2);
    mergeSort(begin, middle);
    mergeSort(middle, end);
    merge(begin, middle, end);
}

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);
    std::vector<int> aux(distance);

    auto left = begin;
    auto left_bound = middle;
    auto right = middle;
    auto right_bound = end;
    size_t aux_index = 0;

    while (left != left_bound && right != right_bound) {
        if (*right < *left) {
            aux[aux_index++] = *right;
            ++right;
        } else {
            aux[aux_index++] = *left;
            ++left;
        }
    }

    std::copy(left, left_bound, &aux[aux_index]);
    std::copy(right, right_bound, &aux[aux_index]);
    std::copy(aux.begin(), aux.end(), begin);
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }

    std::cout << std::endl;
}

Advice 3

Making the sort more idiomatic (a template) and efficient (double buffer strategy) is not too hard:

template<typename RandomIter1, typename RandomIter2>
void merge(RandomIter1 begin,
           RandomIter1 middle,
           RandomIter1 end,
           RandomIter2 aux) {
    RandomIter1 left = begin;
    RandomIter1 right = middle;
    RandomIter1 left_bound = middle;
    RandomIter1 right_bound = end;

    while (left != left_bound and right != right_bound) {
        if (*right < *left) {
            *aux = *right;
            ++right;
        } else {
            *aux = *left;
            ++left;
        }

        ++aux;
    }

    std::copy(left, left_bound, aux);
    std::copy(right, right_bound, aux);
}

template<typename RandomIter1, typename RandomIter2>
void merge_sort(RandomIter1 source_begin,
                RandomIter1 source_end,
                RandomIter2 target_begin,
                RandomIter2 target_end) {
    auto distance = std::distance(source_begin, source_end);

    if (distance < 2) {
        return;
    }

    RandomIter1 source_middle = source_begin;
    RandomIter2 target_middle = target_begin;
    std::advance(source_middle, distance >> 1); // distance >> 1 is the same as
                                         // distance / 2
    std::advance(target_middle, distance >> 1);

    merge_sort(target_begin,
               target_middle,
               source_begin,
               source_middle);

    merge_sort(target_middle,
               target_end,
               source_middle,
               source_end);

    merge(source_begin,
          source_middle,
          source_end,
          target_begin);
}

template<typename RandomIter>
void merge_sort(RandomIter begin, RandomIter end) {
    auto distance = std::distance(begin, end);

    if (distance < 2) {
        return;
    }

    using value_type = typename std::iterator_traits<RandomIter>::value_type;
    value_type* aux = new value_type[distance];
    std::copy(begin, end, aux);
    merge_sort(aux, aux + distance, begin, end);
    delete[] aux;
}

When I compare the above to your version (demo here), I get the following figures when using -O3 optimization flag:

OP time: 377 milliseconds.
coderodde time: 144 milliseconds.
Algorithms agree: true

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Why isn't mergeSort a template? Same for merge? That would make more sense, as the only requirement for those functions is that the iterators are RandomAccessIterators. \$\endgroup\$ – Rakete1111 Jan 29 '17 at 21:10
  • \$\begingroup\$ I assumed the style of OP. Gonna provide template version soon. \$\endgroup\$ – coderodde Jan 30 '17 at 1:05
  • \$\begingroup\$ @Rakete1111 Done! \$\endgroup\$ – coderodde Jan 30 '17 at 6:03

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.