归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。将两个的有序数列合并成一个有序数列，我们称之为"归并"。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；
1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。(参考下面的图片)

2. 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。
下面的图片很清晰的反映了"从下往上"和"从上往下"的归并排序的区别。(以下资料来自：skywang12345)

通过"从上往下的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时：
1. 将数组{80,30,60,40,20,10,50,70}看作由两个有序的子数组{80,30,60,40}和{20,10,50,70}组成。对两个有序子树组进行排序即可。
2. 将子数组{80,30,60,40}看作由两个有序的子数组{80,30}和{60,40}组成。
将子数组{20,10,50,70}看作由两个有序的子数组{20,10}和{50,70}组成。
3. 将子数组{80,30}看作由两个有序的子数组{80}和{30}组成。
将子数组{60,40}看作由两个有序的子数组{60}和{40}组成。
将子数组{20,10}看作由两个有序的子数组{20}和{10}组成。
将子数组{50,70}看作由两个有序的子数组{50}和{70}组成。

通过"从下往上的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时：
1. 将数组{80,30,60,40,20,10,50,70}看作由8个有序的子数组{80},{30},{60},{40},{20},{10},{50}和{70}组成。
2. 将这8个有序的子数列两两合并。得到4个有序的子树列{30,80},{40,60},{10,20}和{50,70}。
3. 将这4个有序的子数列两两合并。得到2个有序的子树列{30,40,60,80}和{10,20,50,70}。
4. 将这2个有序的子数列两两合并。得到1个有序的子树列{10,20,30,40,50,60,70,80}。

算法步骤

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4、重复步骤 3 直到某一指针达到序列尾；

5、将另一序列剩下的所有元素直接复制到合并序列尾。

下面借助分而治之的文章加深理解

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。（以下资料来自：分而治之）

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

易语言实现归并排序

借助前面的资料，我们已经对归并有一个简单的了解，并且感性的知道了分治的方法，下面易语言来实现，难度教大：

merge

.版本 2
.子程序 merge, , , 归并排序(从上往下)代码
.参数 start, 整数型, , 左位置,第1个有序区间的起始地址。
.参数 end, 整数型, , 右位置第2个有序区间的结束地址。
.参数 mid, 整数型, , 中间位置第1个有序区间的结束地址。也是第2个有序区间的起始地址。
.参数 stb, 逻辑型
.参数 a, 整数型, 参考 数组
.局部变量 i, 整数型
.局部变量 j, 整数型
.局部变量 k, 整数型
.局部变量 temp, 整数型, , "0", tmp是汇总2个有序区的临时区域
i ＝ start  ' 第一个有序区的索引
j ＝ mid ＋ 1  ' 第二个有序区的索引
k ＝ 0  ' 临时区域的索引
重定义数组 (temp, 假, 取数组下标 (a, ))
.判断循环首 (i ≤ mid 且 j ≤ end)
    .如果 (stb)
        .如果 (a [i] ＜ a [j])
            k ＝ k ＋ 1
            temp [k] ＝ a [i]
            i ＝ i ＋ 1
        .否则
            .如果真 (a [i] ≠ a [j])
                rsvnum ＝ rsvnum ＋ mid ＋ 1 － i
            .如果真结束
            k ＝ k ＋ 1
            temp [k] ＝ a [j]
            j ＝ j ＋ 1
        .如果结束
    .否则
        .如果 (a [i] ＞ a [j])
            k ＝ k ＋ 1
            temp [k] ＝ a [i]
            i ＝ i ＋ 1
        .否则
            .如果真 (a [i] ≠ a [j])
                rsvnum ＝ rsvnum ＋ mid ＋ 1 － i
            .如果真结束
            k ＝ k ＋ 1
            temp [k] ＝ a [j]
            j ＝ j ＋ 1
        .如果结束
    .如果结束
.判断循环尾 ()
.判断循环首 (i ≤ mid)
    k ＝ k ＋ 1
    temp [k] ＝ a [i]
    i ＝ i ＋ 1
.判断循环尾 ()
.判断循环首 (j ≤ end)
    k ＝ k ＋ 1
    temp [k] ＝ a [j]
    j ＝ j ＋ 1
.判断循环尾 ()
' // 将排序后的元素，全部都整合到数组a中。
.变量循环首 (start, end, 1, i)
    a [i] ＝ temp [i － start ＋ 1]
.变量循环尾 ()

mergesort

.版本 2
.子程序 mergesort, 整数型
.参数 array, 整数型, 参考 数组
.参数 l, 整数型, , 左
.参数 r, 整数型, , 右
.参数 sort, 逻辑型
.局部变量 mid, 整数型
.如果真 (l ＝ r)
    返回 (0)
.如果真结束
mid ＝ (l ＋ r) ＼ 2
mergesort (array, l, mid, sort)  ' 左边有序
mergesort (array, mid ＋ 1, r, sort)  ' 右边有序
merge (l, r, mid, sort, array)  ' 合并两个有序数组
返回 (rsvnum)

归并排序

.版本 2
.子程序 归并排序, 整数型, 公开, 返回逆序对数量
.参数 array, 整数型, 参考 数组
.参数 sort, 逻辑型, , 真从小到大
.局部变量 l, 整数型
.局部变量 r, 整数型
l ＝ 1
r ＝ 取数组成员数 (array)
返回 (mergesort (array, l, r, sort))

测试

.版本 2
.支持库 spec
.局部变量 a, 整数型, , "0"
a ＝ { 12, 33, 56, 89, 78, 521, -60, 1, 92, 11, -23, 89 }
调试输出 (归并排序 (a, 真))
调试输出 (a)

数组:12{-60,-23,1,11,12,33,56,78,89,89,92,521}