代码

#include <algorithm>
template<size_t MAX_LEN=1<<23>
struct Merge
{
    enum:size_t
    {
        half_len=MAX_LEN/2
    }
    ;
    using half_merge=Merge<half_len>;
    //返回值表示是否是out有序
    template<typename It>
    static bool sort(It in,It out,size_t len)
    {
        len = std::min(MAX_LEN,len);
        size_t len1=std::min(MAX_LEN/2,len);
        bool ret0 = half_merge::sort(in,out,len1),ret1=false;
        if(len>half_len)
        {
            ret1=half_merge::sort(in+half_len,out+half_len,len-half_len);
        }
        else
        {
            return ret0;
        }
        It it1,it1_end,it2,it2_end;
        if(ret0)
        {
            std::swap(in,out);
        }
        it1 = in, it1_end=in+half_len;
        it2 = ret0==ret1?it1:out;
        it2_end = it2+len;
        it2 = it2+half_len;
        while (it1 < it1_end && it2 < it2_end)
        {
            if (*it1 < *it2)
            {
                *out = *it1;
                out++;
                it1++;
            }
            else
            {
                *out = *it2;
                out++;
                it2++;
            }
        }
        if (it1 < it1_end)
        {
            std::copy(it1, it1_end,out);
        }
        if (it2 < it2_end&ret0==ret1)
        {
            std::copy(it2, it2_end, out);
        }
        return !ret0;
    }
}
;
template<>
struct Merge<8>
{
    template <typename T>
    static void insert_sort(T ary, size_t len)
    {
        for (size_t i = 1;i < len;i++)
        {
            size_t j = i;
            auto cur = ary[i];
            while (j > 0)
            {
                auto next = ary[j - 1];
                if (cur < next)
                {
                    std::swap(ary[j], ary[j - 1]);
                }
                else
                {
                    cur = next;
                }
                j--;
            }
        }
    }
    template<typename It>
    static bool sort(It in,It out,size_t len)
    {
        insert_sort(in,len);
        return false;
    }
}
;
template <typename Ty>
constexpr Ty ret_zero(Ty *)
{
    return Ty{
    0}
    ;
}
template <typename T>
void merge_sort(T begin, T end)
{
    std::vector<decltype(ret_zero(begin))> work(end - begin);
    bool ret=Merge<1<<24>::sort(begin, work.data(),end-begin);
    if(ret)
    {
        std::copy(work.begin(),work.end(),begin);
    }
    /*
    merge_sort_subproc(begin,end,work.data(),false);
    std::copy(work.begin(),work.end(),begin);
    */
}
void sort(unsigned *a, int n) {
	Merge<1<<27>::sort(a,a+n);
}

评测结果