归并排序是一种利用了分治思想的一种算法，是我在白书上看到的一种高效的排序算法，因此学习一下，并在此做下总结，加深理解。（毕竟也不能老是用sort不是？）

首先由此算法我了解到了一种分治三步法的一种概念（一直对于这些东西云里雾里啊T T）。划分问题，递归求解，合并问题。而归并排序则非常清晰地完成了这三步。划分问题便是想要尽可能的把数组分为两半，使之变为两个较小的问题。递归便是不断地将问题划分地更小。而合并便是问题的关键所在了。假设现在最初的两部分已经排序成功，那么A,B两集合必然是有序的。因此我们便可以贪婪地取两个数组中最小的数来构成一个新的集合，而这个集合便是排序好了的。如｛1，5，7，8｝与｛2，9，10，11｝，先取1，2与5比较取2，5与9比较取5，7与9比较取7……直到两个集合都为空为止。OK，那么合并的问题就大功告成了。

#include<cstdio>

#include<cstring>

const int SIZE=1000;

int a[SIZE],t[SIZE];

int cnt=0;

void merge_sort(int x,int y)

{

    if(y-x>1)//递归边界，当元素个数为2的时候即不再递归y-x+1>2

    {

        int m=(x+y)/2;

        int p=x,q=m,i=x;

        merge_sort(x,m);

        merge_sort(m,y);

        while(p<m||q<y)//当A,B两集合不全为空的时候

        {

            if(q>=y||(p<m&&a[p]<=a[q])) t[i++]=a[p++];//当集合B为空时或者集合A，B不为空均不为空时且A中队首元素较大时

             else {t[i++]=a[q++];cnt+=m-p;}//cnt求的是逆序对数

        }

        for(i=x;i<y;i++) a[i]=t[i];

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=0;i<n;i++) scanf("%d",&a[i]);

        cnt=0;

        merge_sort(0,n); //为什么是0~n呢？因为最后一位数是会不参与排序的(q<y)

        for(int i=0;i<n;i++)

            printf("%d ",a[i]);

        printf("%d\n",cnt);

    }

    return 0;

}