思路
归并排序（MergeSort），是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
实现
递归法: 自顶向下（Top-Down）
直接在原序列上直接归并排序，每次归并排序分别对左右两边进行归并排序，直至细分到两两分组。
迭代法：自底向上（Bottom-Up）
假设序列共有n个元素：
1. 先相邻两两分组进行归并排序
2. 再相邻四四分组进行归并排序
3. 再相邻八八分组进行归并排序
4. 重复扩大分组规模，直到所有元素排序完毕
5. …
复杂度
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
最优时间复杂度：O(nlogn)
最坏空间复杂度：O(n)
图解
来源：
来源：维基百科
来源：维基百科
python实现
递归法: 自顶向下（Top-Down）
def MergeSort(arr):'''1.自顶向下递归实现'''n = len(arr)_mergeSort(arr, 0, n-1) # 顶部开始： 先对[0,n-1]范围内进行递归排序def _mergeSort(arr,l,r):# 终止迭代的条件if l>=r:returnmid = l+(r-l)//2 # (l+r)//2 的改进算法，防止l+r太大溢出_mergeSort(arr,l,mid) # 对左半边arr[l...mid]归并排序_mergeSort(arr,mid+1,r) # 对右半边arr[mid+1...r]归并排序_merge(arr,l,mid,r)# 合并之def _merge(arr,l,mid,r):'''将arr[l...mid]和arr[mid+1...r]两部分进行归并'''# 额外开辟空间，拷贝arr[l,..,r]到aux数组，然后在原arr上赋值操作aux = arr[l:r+1]i ,j = l, mid+1 # 从各自左边开始扫描# k 指向当前为arr赋值的位置for k in range(l,r+1):# 边界判断if i > mid:arr[k] = aux[j-l]j +=1elif j > r:arr[k] = aux[i-l]i += 1elif aux[i-l] < aux[j-l]:arr[k] = aux[i-l]i += 1else:arr[k] = aux[j-l]j += 1
递归法: 自顶向下（改进版）
改进1：归并到小规模数据时，直接调用插入排序。（因为对小规模数组,使用插入排序更高效）
改进2：对于arr[mid] <= arr[mid+1]的情况,无需merge
def MergeSort(arr):'''2.自顶向下递归实现（改进）'''n = len(arr)_mergeSort(arr, 0, n-1) # 顶部开始： 先对[0,n-1]范围内进行递归排序def _mergeSort(arr,l,r):if l>=r:return# 改进1：对于小规模数组,使用插入排序更高效# from SortFunctions import InsertionSort# if r-l <= 15:# insertionSort(arr, l, r)# returnmid = (r+l)//2 # (l+r)/2 的改进算法，防止l+r太大溢出_mergeSort2(arr,l,mid) # 对左半边arr[l...mid]归并排序_mergeSort2(arr,mid+1,r) # 对右半边arr[mid+1...r]归并排序# 改进2：对于arr[mid] <= arr[mid+1]的情况,无需merge# 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失if arr[mid] > arr[mid+1]:_merge(arr,l,mid,r)
_merge()函数上面已定义，直接上面的就好，这里为了节省篇幅，不再定义
对于改进1，经本人实测，在python3的环境下，并没有提升速度，所以我还是注释掉了。
迭代法：自底向上（Bottom-Up）
def MergeSort(arr):'''3.自底向上迭代实现'''# 逐层迭代，从最底层开始，sz = 1 → n 为待合并数组的长度sz = 1while sz <= n:# 每层，从左往右两两归并，i = 0 → n-1i = 0while i<n:# 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并_merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1))i += sz+sz # 跳到下一对sz += sz
_merge()函数上面已定义，直接上面的就好，这里为了节省篇幅，不再定义
