1.归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略
2.归并排序是稳定排序
3.归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
例子：
注：逆序对在代码标注中
关于归并排序求逆序对原理，请自行百度
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #define ll long long 9 #define DB double 10 #define inf 214748360000 11 #define mod 1000000007 12 using namespace std; 13 const int N=1e5+90; 14 int n,a[N*60],b[N*60]; 15 ll ans;//ans为逆序对个数 16 void merge_sort(int l,int r) 17 { 18 if(l==r) return; 19 int mid=(l+r)/2,i,j,k; 20 i=l;k=l;j=mid+1; 21 merge_sort(l,mid); 22 merge_sort(mid+1,r); 23 while(i<=mid && j<=r) 24 { 25 if(a[i]<=a[j]) b[k++]=a[i++]; 26 else ans+=mid-i+1,b[k++]=a[j++]; 27 } 28 while(i<=mid) b[k++]=a[i++]; 29 while(j<=r) b[k++]=a[j++]; 30 for(int o=l;o<=r;++o) a[o]=b[o]; 31 } 32 int main() 33 { 34 scanf("%d",&n); 35 for(int i=1;i<=n;++i) scanf("%d",&a[i]); 36 merge_sort(1,n); 37 for(int i=1;i<=n;++i) printf("%d ",a[i]); 38 // printf("%lld",ans); 39 return 0; 40 }