一、归并排序基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

分解：将列表越分越小，直至分成一个元素。

一个元素是有序的。

合并：将两个有序列表归并，列表越来越大。

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

二、合并相邻有序子序列过程

三、归并排序代码

1、一次归并代码

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[i])            			i += 1        		else:            			ltmp.append(li[j])            			j += 1    	while i <= mid:        		ltmp.append(li[i])        		i += 1    	while j <= high:        		ltmp.append(li[j])        		j += 1    	li[low:high + 1] = ltmp

2、归并排序

def _merge_sort(li，low，high)：	if low < high：#至少两个元素		mid = (low + high) // 2		_merge_sort(li，low，mid)		_merge_sort(li,mid+1,high)		#merage(li,low,mid,high)		print(li[low:high+1])

四、归并排序性能分析

 

四、快速排序、堆排序、归并排序-小结