原理
- 假设初始序列含有n个记录，则可以看成是n个有序的子序列;
- 每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……;
- 如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
-
比如将无序序列 {5,2,9,1,4,7,8,3} 归并排序的流程如下图所示：
递归方式实现
先将无序序列拆分为两个有序的子序列，然后在将
两个有序的子序列进行归并排序;
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-3.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-4.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-5.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-6.png" width="500" />
非递归方式实现
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-7.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-8.png" width="500" />
时间复杂度为：O(nlogn)
是最稳定的排序算法
完整代码地址
