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 &lt;iostream&gt;
#include &lt;vector&gt;

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

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

    std::vector&lt;int&gt; v;

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

    std::vector&lt;int&gt; vLeft(leftVectorSize);
    std::vector&lt;int&gt; vRight(rightVectorSize);

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

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

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

    // Compare and merge
    while (i != vLeft.end() &amp;&amp; j != vRight.end()) {
        if (*i &lt;= *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&lt;int&gt; &amp;v) {
    for (const auto &amp;i : v) {
        std::cout &lt;&lt; i &lt;&lt; "\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 &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;

void mergeSort(std::vector&lt;int&gt;::iterator begin,
               std::vector&lt;int&gt;::iterator end);

void merge(std::vector&lt;int&gt;::iterator begin,
           std::vector&lt;int&gt;::iterator middle,
           std::vector&lt;int&gt;::iterator end);

void print(const std::vector&lt;int&gt; &amp;v);

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

    std::vector&lt;int&gt; v;

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

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

    return 0;
}

void mergeSort(std::vector&lt;int&gt;::iterator begin, std::vector&lt;int&gt;::iterator end) {
    auto distance = std::distance(begin, end);

    if (distance &lt; 2) {
        return;
    }

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

void merge(std::vector&lt;int&gt;::iterator begin,
           std::vector&lt;int&gt;::iterator middle,
           std::vector&lt;int&gt;::iterator end) {
    auto distance = std::distance(begin, end);
    std::vector&lt;int&gt; 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 &amp;&amp; right != right_bound) {
        if (*right &lt; *left) {
            aux[aux_index++] = *right;
            ++right;
        } else {
            aux[aux_index++] = *left;
            ++left;
        }
    }

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

void print(const std::vector&lt;int&gt; &amp;v) {
    for (const auto &amp;i : v) {
        std::cout &lt;&lt; i &lt;&lt; " ";
    }

    std::cout &lt;&lt; std::endl;
}


Advice 3

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

template&lt;typename RandomIter1, typename RandomIter2&gt;
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 &lt; *left) {
            *aux = *right;
            ++right;
        } else {
            *aux = *left;
            ++left;
        }

        ++aux;
    }

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

template&lt;typename RandomIter1, typename RandomIter2&gt;
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 &lt; 2) {
        return;
    }

    RandomIter1 source_middle = source_begin;
    RandomIter2 target_middle = target_begin;
    std::advance(source_middle, distance &gt;&gt; 1); // distance &gt;&gt; 1 is the same as
                                         // distance / 2
    std::advance(target_middle, distance &gt;&gt; 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&lt;typename RandomIter&gt;
void merge_sort(RandomIter begin, RandomIter end) {
    auto distance = std::distance(begin, end);

    if (distance &lt; 2) {
        return;
    }

    using value_type = typename std::iterator_traits&lt;RandomIter&gt;::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.