归并排序是基于分治法的排序方法，其时间复杂度为O（nlogn）
没什么比一张Gif图片来解释排序算法更清爽了。
所以我就从Python的教程网站上扒了一张233
可以看到，归并排序，顾名思义。归，并。
由于形式纷杂不好统一，这里仅列举一种展现方法。但其精髓仍是归与并的分治思想。
void merge(int l,int r) { if(l>=r) return; int mid=(l+r)/2; merge(l,mid); merge(mid+1,r); int i=l,j=mid+1,k=l-1;//此时的i是第一个数组的左端点，j是第二数组的左端点 while(i<=mid&&j<=r) { k++; if(f[i]>f[j]) { //拿两个的首项做对比，小的直接排入。 f1[k]=f[j]; ans+=mid-i+1; ans%=mod; j++; } else { f1[k]=f[i]; i++; } } while(i<=mid){k++;f1[k]=f[i];i++;}//处理剩余 while(j<=r){k++;f1[k]=f[j];j++;} for(int i=l;i<=r;i++) {//这里，归。 f[i]=f1[i]; } }
归并排序常被应用于关于逆序对的问题中。什么是逆序对问题？
对于一个序列a，若i<j且有A[i]>A[j]，则称A[i]、A[j]构成逆序对
归并排序每次把序列二分，递归对左右俩半排序，然后合并两个有序序列。在对左右两半排序时，可以把左右两半各自内部的逆序对数作为子问题计算。故只需考虑“左边一半里一个较大的数”与“右边一半里一个较小的数”构成逆序对的情形。求出这种情形的个数。
在合并时，比较A[i]与A[j]的大小。如若A[j]小，那么A[i]~A[mid]都大于A[j]。他们都会与A[j]构成逆序对。可以顺便统计到答案中去。
代码实现如下：
void merge(int l,int mid,int r){ //合并a[l~mid]与a[mid+1~r] //a是待排序数组，b是临时数组，cnt是逆序对的个数 int i=l,j=mid+1; for(int k=l;k<=r;k++){ if(j>r||i<=mid&&a[i]<=a[j]){ b[k]=a[i++]; } else{ b[k]=a[j++]; cnt+=mid-i+1; } } for(int k=l;k<=r;k++){ a[k]=b[k]; } }
原文：https://www.cnblogs.com/Uninstalllingyi/p/11186426.html