Merge sort C++14 implementation

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 
#include 

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

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

    std::vector 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 &v, std::vector::iterator p, std::vector::iterator r) {
    // Base case: if (p >= r) then return
    if (p  &v, std::vector::iterator p, std::vector::iterator q, std::vector::iterator r) {
    std::vector::size_type leftVectorSize = q - p + 1;
    std::vector::size_type rightVectorSize = r - q;

    std::vector vLeft(leftVectorSize);
    std::vector 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  &v) {
    for (const auto &i : v) {
        std::cout << i << "\n";
    }
}

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 
#include 
#include 
#include 

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

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

void print(const std::vector &v);

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

    std::vector 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::iterator begin, std::vector::iterator end) {
    auto distance = std::distance(begin, end);

    if (distance ::iterator begin,
           std::vector::iterator middle,
           std::vector::iterator end) {
    auto distance = std::distance(begin, end);
    std::vector 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  &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
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 
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 > 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
void merge_sort(RandomIter begin, RandomIter end) {
    auto distance = std::distance(begin, end);

    if (distance ::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.

StackExchange Code Review Q#153900, answer score: 6