猫史档案馆

在学习归并排序之前，我们要了解一个概念——归并

现在给你一个数组，要你进行排序：[6,6,4,6,2,9,5,2,10,1]

假如把它平均分成两半，并且已排序：[2,4,6,6,6][1,2,5,9,10]

怎么得到一整个有序的序列呢？（时间复杂度不得超过O(n)）

简单地交叉两个序列是行不通的：[2,1,4,2,6,5,6,9,6,10]（有多处倒序）

那么可以新建一个序列：[]

将待排序列的两个小序列的第一项中最小的去掉：[2,4,6,6,6][2,5,9,10]

再加入新序列：[1]

这时遇到了相同的数字，应以左边的为较小数字

再删除并加入新序列：[1,2]

重复此过程，可以得到：

待排序列：[4,6,6,6][5,9,10] 新序列：[1,2,2]

待排序列：[6,6,6][5,9,10] 新序列：[1,2,2,4]

......

到最后，待排序列：[][9,10]，新序列：[1,2,2,4,5,6,6,6]

这时有一个小序列为空，此时将另一个小序列的数字全部删除并加入到新序列即可

新序列已经排好序了：[1,2,2,4,5,6,6,6,9,10]，此时复制到旧序列中即可

但是两半部分怎么排序呢？这就需要我们继续拆分了

回到原来的序列：[6,6,4,6,2,9,5,2,10,1]

将其和上次一样平均分成两半，也就是：[6,6,4,6,2][9,5,2,10,1]

这时两个序列项目数为奇数，没办法平均分成两半，怎么办呢？

其实，差不多就可以了，可以左边比右边多一项：[6,6,4][6,2][9,5,2][10,1]

重复此过程，也就是：

待排序列拆分情况：[6,6][4][6][2][9,5][2][10][1]

待排序列拆分情况：[6][6][4][6][2][9][5][2][10][1]

这时每个小序列只有一项，小序列显然已经排好了，就可以合并了

由于上面的[6,6]被拆分成[6][6]，所以[6][6]需要合并

由于上面的[9,5]被拆分成[9][5]，所以[9][5]需要合并

合并后，序列为：[6,6][4][6][2][5,9][2][10][1]

由于再上面的[6,6,4]被拆分成[6,6][4]，所以[6,6][4]需要合并

又由于再上面的[6,2]被拆分成[6][2]，所以[6][2]需要合并

总之，上面怎么拆，下面就怎么合

这样，待排序列就是：[4,6,6][2,6][2,5,9][1,10]

重复此过程，就可以得到完整的序列

递归实现函数：

#调用时，应采用 储存已排序序列的序列=merge(待排序序列,0,len(待排序序列)-1) 的格式
def merge(list1,left,right):
    if left==right:#检测序列是否只有一项
        return list1
    mid=left+(right-left)//2#分出左半部分和右半部分的界限
    list1=merge(list1,left,mid)
    list1=merge(list1,mid+1,right)#递归，排序左半部分和右半部分
    list2=[]
    num=left
    num2=mid+1#初始化归并
    while num<=mid or num2<=right:
        if num>mid:#检查第一个小序列还有没有数
            list2.append(list1[num2])
            num2+=1
        elif num2>right:#检查第二个小序列还有没有数
            list2.append(list1[num])
            num+=1
        elif list1[num2]<list1[num]#比较大小
            list2.append(list1[num2])
            num2+=1
        else:#否则
            list2.append(list1[num])
            num+=1
    num=0#准备将排好的序列复制回去
    while left+num<=right:
        list1[left+num]=list2[num]
        num+=1
    return list1#不要忘记返回