https://en.wikipedia.org/wiki/Merge_sort

merge_sort.cpp

template< typename T >
class Solution
{
    using Vector = vector< T >;
    using Iter = typename Vector::iterator;

    Vector go( Vector&& A )
    {
        auto N{ A.size() };
        if( N < 2 ) return A;
        auto pivot{ A.cbegin() + N / 2 };
        return merge( go({ A.cbegin(), pivot }), go({ pivot, A.cend() }) );
    }

    Vector merge( const Vector& lhs, const Vector& rhs, Vector res={} )
    {
        auto i{ lhs.cbegin() }, j{ rhs.cbegin() };
        while( i < lhs.cend() && j < rhs.cend() ) res.push_back( ( *i < *j )? *i++ : *j++ );
        if( i != lhs.cend() ) res.insert( res.end(), i, lhs.cend() );
        if( j != rhs.cend() ) res.insert( res.end(), j, rhs.cend() );
        return res;
    }

public:

    Vector mergeSort( const Vector& A )
    {
        return go({ A.cbegin(), A.cend() });
    }

};