Generic Merge Sort in C++ I wanted to implement merge sort in a generic way. I was not sure whether I should use the iterator or the container for the template type. I did not find a way to infer the container type using iterator_traits, so I decided to use the templated type for the container. Please let me know what you think!

#include &lt;iostream&gt;
#include &lt;vector&gt;

using namespace std;

template&lt;typename T&gt;
void printArray(const T&amp; a) {
    for (auto i: a) {
        cout &lt;&lt; i &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
}

template&lt;typename T&gt;
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n &lt; 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort&lt;T&gt;(begin, begin + n/2);
    auto secondHalf = mergeSort&lt;T&gt;(begin + n/2, end);
    auto firstIt = firstHalf.begin();
    auto secondIt = secondHalf.begin();
    T merged;
    while (firstIt != firstHalf.end() &amp;&amp; secondIt != secondHalf.end()) {
        if (*firstIt &lt; *secondIt) {
            merged.push_back(*firstIt);
            ++firstIt;
        } else {
            merged.push_back(*secondIt);
            ++secondIt;
        }
    }
    while(firstIt != firstHalf.end()) {
        merged.push_back(*firstIt);
        ++firstIt;
    }
    while(secondIt != secondHalf.end()) {
        merged.push_back(*secondIt);
        ++secondIt;
    }
    return merged;
}

int main() {
    vector&lt;int&gt; a = {3, 0, 7, 5, 7, 8, 3, 1};
    printArray(mergeSort&lt;vector&lt;int&gt;&gt;(a.begin(), a.end()));
    return 0;
}
While your merge step in mergeSort works it should be put into its own function:

// Exercise: make `my_merge` even more generic
template &lt;typename Iterator, typename OutputIterator&gt;
void my_merge(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              OutputIterator out)
{
    while (first1 != last1 &amp;&amp; first2 != last2) {
        if (*first1 &lt; *first2) {
            *out++ = *first1++;
        } else {
            *out++ = *first2++;
        }
    }

    while(first1 != last1) {
        *out++ = *first1++;
    }
    while(first2 != last2) {
        *out++ = *first2++;
    }
}

template&lt;typename T&gt;
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n &lt; 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort&lt;T&gt;(begin, begin + n/2);
    auto secondHalf = mergeSort&lt;T&gt;(begin + n/2, end);

    T merged;

    my_merge(firstHalf.begin(), firstHalf.end(), 
             secondHalf.begin(), secondHalf.end(),
             std::back_inserter(merged));
    return merged;
}


Note that I had to call my_merge that way since std already contains std::merge, which we can use instead:

template&lt;typename T&gt;
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n &lt; 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort&lt;T&gt;(begin, begin + n/2);
    auto secondHalf = mergeSort&lt;T&gt;(begin + n/2, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(), 
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}


The merge and the parameters begin and end are good examples why using namespace std has to be handled with care. All those names are already in std. Use using namespace std only if you know the risks.

That being said, your generic variant will only work with random access iterators. If you want to make it more generic, you have to use std::distance and std::next instead of end - begin and begin + n/2:

template&lt;typename T&gt;
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    const auto n = std::distance(begin, end);

    if (n &lt; 2) {
        return T(begin, end);
    }
    const auto midpoint = std::next(begin, n / 2);

    const auto firstHalf  = mergeSort&lt;T&gt;(begin, midpoint);
    const auto secondHalf = mergeSort&lt;T&gt;(midpoint, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(), 
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}


Even if you don't want to use std::next re-use the midpoint.