归并排序的理解：

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

• 分到不能再分才开始解：归并排序一直划分（递归）到排序一个元素（不能再划分）为止。
• 解只是解最小问题的解：归并排序的解不做任何事情。
• 并不是求解具体的最小问题的，只是负责将子问题的答案如何合并：负责将已经得到的两个排好的部分排序是并。

  二、特点

  优点：

  • 外部排序：可以不用一次全部读入
  • 稳定的排序算法：同值的元素保持原来的先后顺序

  缺点：

  • 需要额外创建的空间代价

  时间复杂度： o(nlogn）

• 三、解决的问题

          1.数组进行排序。
???2.计算数组中的逆序对的个数。

          3.交换元素的次数最少

#include
#define ms(a,b) memset(a,b,sizeof(a))
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define ms(a,b)        memset(a,b,sizeof(a)); 
using namespace std;
const int N=100010;
const int maxx = 0x3f3f3f;
const int mod = 1e9+7;
const int minn = -0x3f3f3f;
const int maxn = 400005;
int n,a[10000]={},tmp[10000]={},ans=0; 
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else {
            tmp[k ++ ] = q[j ++ ];
            ans+=mid-i+1;
        }

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
    int i;
    fast;
    cin>>n;
    for (i=1;i<=n;i++){
        cin>>a[i];
    } 
    merge_sort(a,1,n);
    for (i=1;i<=n;i++)    cout<' ';
    cout<ans;
    return 0;
}