template<typename value_type, typename value_Ptr>

int merge_sort(const value_Ptr& begin, const value_Ptr& end)

{

    static std::vector<value_type> to(end - begin);

    static int cnt{  };            //记录逆序对数

    if (end - begin <= )return ;

    value_Ptr mid = begin + (end - begin) / ;

    merge_sort<value_type>(begin, mid);

    merge_sort<value_type>(mid, end);

    //将上述两段区间顺序排列

    value_Ptr l = begin, r = mid;

    int k{  }, index{  };

    while (l < mid && r < end)

        if (*l < *r)to[k++] = *l++;

        else                      //如果左侧值小于右侧

        {

            cnt += mid - l;       //逆序对数记录

            to[k++] = *r++;

        }

    while (l < mid)to[k++] = *l++;

    while (r < end)to[k++] = *r++;

    for (index = ; begin + index < end; ++index)*(begin + index) = to[index];

    return cnt;

}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    int list[]{ ,,,,,,,,, };

    vector<int> v{ list,list +  };

    int cnt = merge_sort<int>(list + , list + );

    merge_sort<int>(v.begin(), v.end());

    for (auto it : v)cout << it << " ";

    cout << endl;

    for (auto it : list)cout << it << " ";

    cout << endl;

    cout << "逆序对数:" << cnt << endl << endl;

    char list_[]{ 'r','c','','A','z','b','','','r', '' };

    vector<char>v_{ list_,list_ +  };

    cnt = merge_sort<char>(list_ + , list_ + );

    merge_sort<char>(v_.begin(), v_.end());

    for (auto it : v_)cout << it << " ";

    cout << endl;

    for (auto it : list_)cout << it << " ";

    cout << endl;

    cout << "逆序对数:" << cnt << endl << endl;

}