归并排序是一个从思路到实现都极其的像快速排序的一个排序算法。同样，归并排序使用的思想也是 分治 思想，大事化小，小事化了。
算法过程
回到我们的那个老问题，什么样的数列是绝对有序的？答案是空数列或者只含有一个数的数列是绝对有序的。归并排序就是先分解再合并，首先把数列通过二分的方式不停的进行分割，直到分割成所有的数列中的数都被拆开（这样没一个分出来的子数列就是绝对有序的），然后两两进行合并组成新的数列，再和其他的用同样方式组成的数列合并……直到最后，整个数列被合并为之前的数量，整个数列就排序完成。
如下图的上半部分，我们将原始数列经过几次的从中间拆分成两部分的操作，最终将数列 拆无可拆 ，变成了数列中所有的数都 “各自为战” ，这些各自为战的每一个数就是一个有序数列（就自己一个，当然是有序的）。
如下图的下半部分，我们将经过第一步拆分成各自为战的各个小的“数列”（单个的数）依次两两进行合并。这个过程就是将 两个有序数列 合并成 一个有序数列 的过程。合并到最后，并无可并 的时候，所有的数此时都被重新排列了，整个数列完成了排序，全部有序！
归并排序先分解再合并过程图.png
拆分的时候，比较容易拆分，我们合并的时候怎么合并呢？合并就是把两个有序数列合并成一个有序数列的过程。这个过程的具体操作如下图所示：
假设下图左侧的上下两个数列就是待合并的两个数列，右侧的数列就是合并之后的效果。右边的效果的合并过程，就如图中曲线中间的标号顺序：
- 设左侧上边数列为【1】，下边数列为【2】，右边的数列为合并后的新数列。（注意：【1】、【2】都是有序的）
- 比较【1】、【2】的第 1 个位置，2 < 7，因此，将【2】中的第一个数 2 移动到右边的新数列的第 1 个位置，【2】中的第 1 个数找到了归宿。
- 把还没有找到归宿的【2】的第 2 个数和【1】的第一个数比较，4 < 7, 因此将【2】中的第 2 个数 4 移动到右边新数列的第 2 个位置，【2】中的第 2 个数找到了归宿。
…… - 就是这样，【1】【2】中每找到一个数的归宿，就用这个数后面的数拿出来去比较，然后小的数移动到新的数列中。最终我们发现，其中一个数列会被 “搬空” ，就是我们这里的【2】。而【1】中还剩余两个数 10、12 。当出现 “搬空” 的时候，我们就把另外一个没被 “搬空” 的数列剩余的所有的数，原封不动的移动到新的数列的最后去。
- 最终我们发现，我们在这样的交叉=>比较=>后移=>比较中，把两个有序数列【1】、【2】合并成了一个新的有序数列。这就是合并两个有序数列为一个有序数列的方法。
合并两个有序数组的过程图.png
最终，通过先拆分，再合并，合并的过程中借助一个两两合并有序数列的方法，我们完成了最终的归并排序的全过程，我们的原始数列被排序完成！
算法实现
#coding:utf-8
import numpy as np
# 归并排序
def merge_sort(data):
merge_sort_content(data, 0, len(data)-1)
# 递归进行归并排序的实体部分
def merge_sort_content(data, f, t):
if f >= t:
return
center = (f + t) // 2
merge_sort_content(data, f, center)
merge_sort_content(data, center+1, t)
merge(data, f, center, t)
# 合并数组中的两部分
def merge(data, f, c, t):
i = f
j = c + 1
temp = []
# 把最小的依次放入临时数组中，此处需要额外开辟空间，所以归并排序不是就地排序，需要额外空间
while i <= c and j <= t:
if data[i] < data[j]:
temp.append(data[i])
i += 1
else:
temp.append(data[j])
j += 1
# 把没有挪完到临时数组的部分，挪到临时数组
start = i
end = c
if j <= t:
start = j
end = t
for k in range(start, end+1): # python的区间是左闭右开
temp.append(data[k])
# 把临时数组中的数，都拷贝回排序的区间上去
data[f:t+1] = temp
array = np.arange(20)
np.random.shuffle(array)
array = list(array)
print('输入的数据: {}'.format(array))
merge_sort(array)
print('排序之后的数据：{}'.format(array))
结果是：
归并排序的结果.png
上一篇：写给媳妇儿的算法（六）——快速排序
下一篇：写个媳妇儿的算法（八）——桶排序
