前情提要：我真的好喜欢这个算法啊，感觉学完堆排序其他的都充满光明与希望。
简而言之，一个列表分成两半，对两段分别遍历，谁小谁出来，最后使得两段有序列表变为一段有序列表，这个过程叫一次归并。
比大小，1出来 ，j箭头右移到3下方
比大小，2出来，i箭头右移到5下方，以此类推
到一边全部遍历完之后，另外一边的数直接全部导入新列表即可
以下三个红色箭头从左至右分别代表low， mid， high
算法思路
第一要义是先写出归并算法，根据上面分析可得：
def merge(li,low,mid,high):
i=low
j=mid+1
ltmp=[]
while i<=mid and j<=high:#只要左右两边都有数
if li[i]>li[j]:
ltmp.append(li[j])
j+=1
else:
ltmp.append(li[i])
i+=1
#while执行完，肯定有一部分没数了
while i<=mid:
ltmp.append(li[i])
i+=1
while j<=high:
ltmp.append(li[j])
j+=1
li[low:high+1]=ltmp
递归的部分（排序部分）分为三步：1.递归左边 2.递归右边 3.归并左右
算法实现
def merge_sort(li,low,high):
if low < high:#至少有两个元素，递归
mid=(low+high)//2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
完整程序如下
def merge(li,low,mid,high):
i=low
j=mid+1
ltmp=[]
while i<=mid and j<=high:#只要左右两边都有数
if li[i]>li[j]:
ltmp.append(li[j])
j+=1
else:
ltmp.append(li[i])
i+=1
#while执行完，肯定有一部分没数了
while i<=mid:
ltmp.append(li[i])
i+=1
while j<=high:
ltmp.append(li[j])
j+=1
li[low:high+1]=ltmp
def merge_sort(li,low,high):
if low < high:#至少有两个元素，递归
mid=(low+high)//2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
#测试段代码
from random import *
from time import *
a=[i for i in range(1000)]
shuffle(a)
start_time=time()
merge_sort(a,0,999)
print(a)
end_time = time()
print(end_time-start_time)
运行结果显示
（超快超棒棒）
时间复杂度O（nlogn）（分两部分遍历列表是n，递归了logn层需要logn）
空间复杂度O（n）（因为要新建一个列表，加之递归要占用内存）
快速排序，堆排序，归并排序小结
c++语言和java都默认sort函数是快排（Java好像改了？）python默认的sort是基于归并排序结合插入排序的一种优化后的新算法
排序的稳定性如何理解？比如说[3,2,1,3,2]这样一个列表，在排序时红色的2相对蓝色的2在蓝色2前面，排序后为保持这样位置关系不变（一定不变）则称为比较稳定，否则则不稳定（有可能变有可能不变）
一般来说，比较类排序算法是挨个换的，比较稳定；而跳着换类型的比如快排就不稳定
部分图片参考自b站IT编程界的扛把子的python算法学习视频，本文仅供个人学习使用，特此声明
