merge_sort是分治法的一个典型应用。这里有一张《各类排序算法时间、空间复杂度对比表》，从表中可以看得出，merge_sort（归并排序算法）是比较稳定的算法，使用较广泛。求逆序对也是很好用的。
分治过程概括图：蓝色的原始数组，运用merge_sort以后为有序的绿色数组
我的理解：主要想说二路归并（大佬请忽略）
1. merge() 是二路归并的阶段，简单来说是有序表的合并。这时有两段：左段 al~amid 和右段 amid+1~ar ，转移数组 c 的下标从 cnt=0 开始，定义左右两段的下标分别为 i 、j ，且 i 指向 al ，j 指向 amid+1 。现在不停地比较 ai 与 aj 的值大小，总是将较小（以升序为例，降序稍加修改，就改三四处）的一个值赋给 c 数组，如果 ai 较小 （ aj 的话，后面改为 j ）,则 i 和 cnt 均 加 1，直到两段其中有一段的长度为零（下标到结尾）。最后，将长度不为零的一段剩下的a值全部给 c 数组，merge() 函数完成。在 a 数组的值给到 c 数组的过程中，我们总是选最小的。实际上，左段和右段都是有序的（或者如图一的第一行绿色只有一个元素），我们每次两两比较又总是取较小的加入 c 数组，所以 c 中的值是严格的由小到大。最后从 cnt=0 开始回给到 a 后，新的 a 数组顺序也是严格的由小到大。
对应code：
const int M=1e5+5;
int a[M];
void Merge(int l,int m,int r)
{
int c[r-l+1];
int i=l,j=m+1;
int cnt=0;
while(i<=m&&j<=r)
{
if(a[i]<=a[j])
c[cnt++]=a[i++];
else
c[cnt++]=a[j++];
}
while(i<=m)
c[cnt++]=a[i++];
while(j<=r)
c[cnt++]=a[j++];
for(int k=0;k<cnt;k++)
a[l++]=c[k];
}
2.sort() 内部使用递归，递归边界：各有序表长度为 1 ，数组分两段进行，然后逐步返回，返回过程调用merge()。最终得到有序表a[ ]；
对应code：
void mergesort(int l,int r)
{
if(l==r)/*!< 递归边界 */
return;
int m=(l+r)/2;/*!< 递归步骤 */
mergesort(l,m);
mergesort(m+1,r);
Merge(l,m,r);/*!< 二路归并 */
}
那么整个算法：
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 const int M=1e5+5; 6 int a[M]; 7 8 void Merge(int l,int m,int r) 9 { 10 int c[r-l+1]; 11 int i=l,j=m+1; 12 int cnt=0; 13 while(i<=m&&j<=r) 14 { 15 if(a[i]<=a[j]) 16 c[cnt++]=a[i++]; 17 else 18 c[cnt++]=a[j++]; 19 } 20 while(i<=m) 21 c[cnt++]=a[i++]; 22 while(j<=r) 23 c[cnt++]=a[j++]; 24 for(int k=0;k<cnt;k++) 25 a[l++]=c[k]; 26 } 27 28 void mergesort(int l,int r) 29 { 30 if(l==r)/*!< 递归边界 */ 31 return; 32 int m=(l+r)/2;/*!< 递归步骤 */ 33 mergesort(l,m); 34 mergesort(m+1,r); 35 Merge(l,m,r);/*!< 二路归并 */ 36 }
PS：这里有两归并可解的题：洛谷【P1177】 模板 快速排序 和 洛谷【P1908】逆序对，供测试。
原文：https://www.cnblogs.com/Ycourage/p/9374027.html