Merge sort C++14 implementation

Question

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";
    }
}

Answer 1

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.