例子
看到这里相信你对归并排序的实现已经有了解，那么我们举出一个实例来带你从头到尾的走一遍归并排序的过程，来看看归并排序是怎么工作的。
一般题目会给出我们一个原数组，例如这样的：
在这里为了大家观看方便我将数组下标放置元素上方 。
第一步，找中间点，分解
中间点的下标是2，那么经过我们分解得到的第一层就是这样的：
第二步 分解。
因为我们发现分开的数组都不是单独的，那么我们继续进行分层，这是我们的第二层 。
第三步 分解
对分开的区域分别进行判断，将未完全分解的数组，进行分解 ，已经成为最小单元的数组就不去进行操作了。
到这里，所有的元素都被我们拆分 。
第四步 归并
由于所有组都已经分解成只有1个元素，开始进行归并，从下向上进行归并，先比较最下一层的两组元素，14 < 27，因此将14排在27前面，由于已经没有元素，结束此次归并，如下图：
第五步 归并
继续向上一层进行归并，这一层有4个组，进行两两比较。首先，比较14、27和36：14 < 36，所以14放第一个位置，接着比较27和36，27 < 36，所以27放第二个位置，此时第一组14、27已经没有元素，于是将36填入14和27之后。接着比较12和31：12 < 31，所以12放第一个位置，由于第一组12已经没有元素，于是将31填入12之后。归并的结果如下：
第六步 归并
继续向上一层进行归并，这一组有2个组，第一组：14、27、36，第二组：12、31。同样的，取两组的第1个数比较：14 > 12，所以12放第1个位置；接着取第二组的第2个数比较：14 < 31，所以14放第2个位置；接着取第一组的第2个数比较：27 < 31，所以27放第3个位置；接着取第一组的第3个数比较：36 > 31，所以31放第4个位置；由于第二组已经没有元素，所以37自然归入第5个位置。此时，归并结束，最终数组如下。
整体流程图
所有整体的流程图就是这样的：
通过上面的细分加上这张图，可以很清晰的了解到归并排序是怎么样去进行实现的了 。
完整动态过程
完整的动态规划过程就是这样的，颜色表示组别，高度表示大小，可以清晰明了的向你展示出归并排序的全部过程 。
实战
第一题 归并排序
题目：
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
思路：
大家通过读题就可以看的出来，这道题目很明显的就是在考察我们归并排序的一个基础，我们只需做好我上面提到三步就可以，第一步：输入；第二步：调用我们的模板；第三步：输出。即可
需要注意的是，我们在调用模板的时候要弄清楚我给的模板，要从主函数之中输入什么就可以了，其余就没有任何难度了 。
AC:
#include <iostream> using namespace std ; const int N = 100010 ; int a[N], temp[N] ; void merge_sort(int a[], int l, int r) //模板 { int mid = (l+r)/2 ; if(l>=r) return ; merge_sort(a, l, mid) ; merge_sort(a, mid+1, r) ; int sum = l, i = l, j = mid+1 ; while(i<=mid && j<=r) { if(a[i] <= a[j]) temp[sum++] = a[i++] ; else temp[sum++] = a[j++] ; } while(i<=mid) temp[sum++] = a[i++] ; while(j<=r) temp[sum++] = a[j++] ; for(int i=l; i<=r; i++) { a[i] = temp[i] ; } } int main() { int n ; //输入 cin >> n ; for(int i=0; i<n; i++) { cin >> a[i] ; } merge_sort(a,0,n-1) ; //调用模板 for(int i=0; i<n; i++) //输出 { cout << a[i] << " " ; } return 0 ; }
第二题 逆序对数量
题目：
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路：
很明显，这道题目的难度就远高于上一道题，并且通过我们读题并不能发现这道题想要考察我们什么，既然我将这道题目放在这里了，那么这道题就是考察的归并排序，但是在比赛的时候，我们要自己通过题目去判断这道题到底考察的什么，所有我们就来分析以下这个题目 。
我们在上面学习归并排序的时候讲到，归并操作是将要将两个有序数组合并为一个有序数组的，那么我们观察将数组一分为二后的两个部分，很明显这两个部分都是有序的，而且第二部分数组对应的数组下标肯定是大于第一部分所对应的数组下标的，有了这两个规律我们进行假设：如果存在a[i]>a[j],首先由于j是在第二部分，那么j大于第一部分的所有下标，其次a[i]>a[j],这也就满足了我们题目中所提到了一对逆序数的条件了，而且两个部分的数组均是递增的，那么第一部分a[i]后面的数也都不会比a[i]小，那么第一部分a[i]以及a[i]后面的数字都可以作为a[j]的逆序对数，这样看来我们a[j]在第一部分的逆序对数量就是：mid-i+1 了。
这个时候肯定会有朋友问，这种情况虽然成立，但不一定唯一啊，也有可能会出现其他情况啊，这应该怎么办啊？
这时我们先从整体数组开始观察，我们将数组中的逆序对数分为三种情况：均在mid点的左边，均在mid点的右边，一左一右 。在图中我也以红黄蓝三种情况去进行了表示。
我们正常思考，如果我们要算逆序对的数量，肯定要将红黄蓝三种情况相加。那么逆序对数量=红色情况+黄色情况+蓝色情况了。
红色情况 = merge_sort(L,mid) ;
蓝色情况 = merge_sort(mid+1,R) ;
黄色情况 = mid-i+1 ;
看到这里你是不是觉得问题已经解决了，然而并没有，看上面三种情况看似都列出的公式，但是只有黄色情况的公式我们在开头已经进行的论证，是完全正确的，红色和蓝色的情况并不一定正确，那么为什么红色与蓝色的数量可以由merge_sort(L,mid)和merge_sort(mid+1,R)去表示呢也就是我们为什么要使用归并排序去进行计算呢？
下面这个图就可以很好的展现出红黄蓝三种情况的组成以及在此基础上去再分解为红黄蓝三种情况的展示 。
我们来分析一下，我们索要的结果由红黄蓝三种部分所组成，而我们红色和蓝色的部分又可以分成由红黄蓝所组成的三种情况，所有我们从下往上去看，我们将数组元素分成只有单个元素的时候，这个时候红色和蓝色的情况就不会存在了，因为mid两边不会存在一个以上的数去让给他们进行比较，所以就不会存在红色和蓝色的情况了，这时我们上推一层就会清楚的发现倒数第二层的红色或蓝色情况也都是由倒数第一层的黄色情况所组成，这样我们依次的去向上推进，就会发现，看似是红+黄+蓝的组合，但其实他的本质确实黄色一种情况 。
那我们为什么要使用归并排序呢，归并排序就可以很好的满足求逆序对数这一特点，我们以及学习了如何去归并排序，归并排序是要将一个数组分解为单个单元之后再去合并的，那么在分解成单个单元之后，我们就不会出现红色和蓝色的情况了，也就是我们在进行归并排序的过程中，只需去考虑黄色的数量，并将黄色的数量逐层累加，这样我们最后就可以得到逆序对数。也正是归并排序有着将数组分为最小单元并且从下向上合二为一的这种性质，所以我们在计算逆序对数时才会选用这种办法。
正是因为逆序对数其数量最后本质上都是黄色情况的总和，所以这也正是我在刚开始就将黄色部分的计算方法做出讲解的原因。 这也就很好的解决一开始去怀疑会出现其他情况的疑问。
AC：
代码部分我们还是使用其模板，但是我们要在模板的基础上去根据我们题目的要求做出一些小小的变更即可，其变更详细内容就见代码区的注释就好。
#include <iostream> using namespace std ; typedef long long LL ; const int N = 100010 ; int a[N] ; int tmp[N] ; LL res = 0 ; //res 就是逆序对数量 LL merge_sort(int a[], int l, int r) //因为这里我们最后要返回逆序对数量，所有我们在这里设置了long long类型 { int mid = l+r>>1 ; //找中间点 if(l>=r) return 0 ; //判断元素个数 res = merge_sort(a, l, mid) + merge_sort(a, mid+1, r) ; //红色和蓝色数量，本质在上面已经讲清楚了 int k=0 , i=l, j=mid+1 ; while(i<=mid && j<=r) { if(a[i] <= a[j]) tmp[k++] = a[i++] ; else { res += mid-i+1 ; //计算我们所说的黄色情况 tmp[k++] = a[j++] ; } } while(i<=mid) tmp[k++] = a[i++] ; while(j<=r) tmp[k++] = a[j++] ; for(int i=l, j=0; i<=r; i++, j++) { a[i] = tmp[j] ; } return res ; } int main() { int n ; //输入 cin >> n ; for(int i=0; i<n; i++) cin >> a[i] ; merge_sort(a,0,n-1) ; //调用模板 cout << res << endl ; //输出 return 0 ; }
结尾
到了这里，我们今天的内容讲解也就结束了，希望大家啊都可以很好的学到这些算法知识，学习算法是日积月累的，所以不要心急，每天学一点，到最后你一定会成功的。对啦，还要记得复习今天所讲的内容噢，特别时模板，要多去熟悉几遍。
