概念

归并排序， 首先我们要了解什么是归并

归并

归并 可以总结为对多个有序列表的有序合并.

比如针对两个有序列表如下

[15,9,4,1]
[98,76,14,7,5]

这两个有序列表合并后的结果是：

[98, 76, 15, 14, 9, 7, 5, 4, 1]

这个过程就是归并.

注意， 这里的列表一定先是有序列表， 方能进行归并,且结果也是有序列表

归并说明

针对两个有序列表 s1,s2， 如何进行归并，过程如下(这里均是倒序排列)

将s1和s2均从第0个元素开始比较， 假如s1的元素值小于s2的元素值，那么将s2的元素值置于一个临时列表s中，并将s2的偏移量向后移动一位, 同理， 假如s1的元素值大于s2的元素值，那么就将s1的元素值添加到临时列表s中，并将s1的偏移量向后移动一位，直到其中某个列表的偏移量越界，那么再将另一个列表的剩余元素直接添加到临时猎列表s中

最终这个s 就是归并好的有序列表

归并实现

def merge(s1,s2):
    s1_index = 0
    s2_index = 0

    s1_len = len(s1)
    s2_len = len(s2)

    s = []
    while s1_index < s1_len and s2_index < s2_len:
        if s1[s1_index] < s2[s2_index]:
            s.append(s2[s2_index])
            s2_index += 1
        else:
            s.append(s1[s1_index])
            s1_index += 1
    if s1_index == s1_len:
        s += s2[s2_index:]
    elif s2_index == s2_len:
        s += s1[s1_index:]
    return s

测试一下

s1 = [15,9,4,1]
s2 = [98,76,14,7,5]

print(merge(s1,s2))

结果如下

[98, 76, 15, 14, 9, 7, 5, 4, 1]

归并排序

讲完了归并， 我们就该说归并排序了，针对一个无序的列表，我们可以将其分割成两两一组的小列表，将每组的这两个小列表进行归并， 这样我们就将原本的列表分成了一个个小的有序列表的集合， 然后我们再对这个集合做分组归并。 通过这种方式将一个大的无序列表分治处理，从而得到最终的排序结果

实现

def merge_sort(s):
    s_len = len(s)
    if s_len < 2:
    	  #只有一个有序列表时即表示排序完成， 返回结果
        return s[0]

    index = 0
    x = []
    while index < s_len:
        if index < (s_len - 1): 
            #如果能两两分组，进行归并
            x.append(merge(s[index],s[index+1]))
        else:
            #(奇数个元素时)，最后的单个元素直接添加
            x.append(s[index])
        index += 2
    return merge_sort(x) #递归处理

测试

x = [128,299,992,2,3,8,3,200,55,18,9,89,43,76,0,-1,-786,343,-65]

在向merge_sort传递参数前， 要将参数列表元素做列表化处理，因为每次归并时都是针对列表做处理的，实际的调用如下

x = [128,299,992,2,3,8,3,200,55,18,9,89,43,76,0,-1,-786,343,-65]
m = [[n] for n in x]
print(merge_sort2(m))

结果如下

[992, 343, 299, 200, 128, 89, 76, 55, 43, 18, 9, 8, 3, 3, 2, 0, -1, -65, -786]