C++ implementation of Merge sort

merge_sort.cpp

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

template<typename Iterator>
std::vector<typename Iterator::value_type> mergeSort(Iterator begin, Iterator end) {
    if (begin == end) {
        return std::vector<typename Iterator::value_type>();
    }
    auto n = std::distance(begin, end);
    if (n == 1) { 
        return std::vector<typename Iterator::value_type>(1, *begin);
    }
    Iterator median = begin;
    std::advance(median, n / 2);
    auto left  = mergeSort(begin,  median);
    auto right = mergeSort(median, end);
    auto itLeft  = left.begin();
    auto itRight = right.begin();
    std::vector<typename Iterator::value_type> merged(left.size() + right.size());
    auto itMerged = merged.begin();

    if (left.back() > right.front()) {
        while (itLeft != left.end() &&  itRight != right.end()) {
            if (*itLeft < *itRight) {
                *itMerged = *itLeft;
                ++itLeft;
            } else {
                *itMerged = *itRight;
                ++itRight;
            }
            ++itMerged;
        }
    }

    itMerged = std::copy(itLeft, left.end(), itMerged);
    std::copy(itRight, right.end(), itMerged);
    return merged;
}