1. 归并排序与分治策略
归并排序的核心思想就是 分而治之。
先介绍下分治法，设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略：对于一个规模为N（N较大）的问题，将其划分为K个规模较小的子问题，若子问题相互独立且与原问题形式相同，我们则可以使用递归不断地将子问题进行划分，将一个大问题自顶向下一层层划分为容易解得小问题，得到小问题的解后再自底向上逐层合并得到原问题的解。
归并排序就是采用了这样的分治策略来设计算法。对于一个长度为N的数组，通过逐层二分将大数组分解成容易排序的小数组，然后对排好序的两个子数组进行归并，最终得到归并后的有序数组。
使用增量策略的排序（如插入排序）的算法复杂度为O(n^2)，而使用分治策略的归并排序则将算法复杂度降到了O(nlogn)。经过测试，这种排序算法的优化效果是很显著的，大家可以在最后看到测试时各种方法所用时间的对比。
2. 自顶向下、自底向上、使用插入排序的归并算法实现
（1）归并算法
有了分治的策略，那么我们如何将排好序的子数组合并成一个有序的数组呢？这就是归并排序的核心算法merge(a,lo,mid,hi)。
对于上图看了代码应该很容易理解：
需要一个辅助数组aux，现将a的元素拷贝给aux，再将aux元素归并到a中。
def __merge(self,a,lo,mid,hi):
i=lo
j=mid+1
self.__aux[lo:hi+1]=a[lo:hi+1] #将a[lo..hi] 复制给aux[lo..hi]
for k in range(lo,hi+1):
if i > mid:#左侧元素归并完毕，将右侧剩余元素依次拷贝到a
a[k] = self.__aux[j]
j+=1
elif j > hi:#右侧，同上
a[k] = self.__aux[i]
i+=1
elif self.less(self.__aux[j],self.__aux[i]):#谁小将谁归并入a
a[k] = self.__aux[j]
j+=1
else:
a[k] = self.__aux[i]
i+=1（2）自顶向下的归并排序
有了以上的归并操作后，我们如何递归地划分数组并将两个子数组排序呢？通过递归直到将子数组划分为长度为1的数组，此时hi <= lo开始return，归并后的数组即是长度为2，4，8，…，n的有序数组。
def __sort_by_recurse(self,a,lo,hi): # 使用递归进行自顶向下归并
if hi <= lo:
return
mid=int((hi+lo)/2)
self.__sort_by_recurse(a,lo,mid)
self.__sort_by_recurse(a,mid+1,hi)
self.__merge(a,lo,mid,hi)（3）自底向上的归并排序
我们同样可以使用循环，从长度为1的数组开始归并，层层向上，这样每次都是两个有序的子数组（长度n/2）归并成一个有序的数组（长度n）。
def __sort_by_loop(self,a): # 使用循环，自底向上归并
sz=1
while sz<len(a):
for lo in range(0,len(a)-sz,sz+sz):
self.__merge(a,lo,lo+sz-1,min(lo+sz+sz-1,len(a)-1))
sz += sz（4）对小规模子数组使用插入排序
递归会使小规模问题中的函数调用过于频繁，而插入排序（或者选择排序）即简单，而且在小数组上可能比归并排序更快。经测试，插入排序子数组的大小在10左右比较合适。
def __merge_with_insertion(self,a): # 对较小的子数组使用插入排序，从而减少归并次数，优化排序算法
sz=min_merge_sz=10 # 归并子数组的最小长度
for i in range(0,len(a),min_merge_sz):
a[i:min(i + min_merge_sz, len(a))] = self.__insertion_sort(a[i:min(i+min_merge_sz, len(a))]) # 对长度小于min_merge_sz的子数组使用插入排序
while sz < len(a):
for lo in range(0, len(a) - sz, sz + sz):
self.__merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, len(a) - 1))
sz += sz3.测试与对比
数组长度为1000
数组长度为10000
数组长度为100000（已无法使用O(n^2)的初级排序）
数组长度为1000000（百万级数组归并排序已经很慢了，需要十几秒）
通过前两个可以验证插入排序O(n^2)的时间复杂度，n没增大10倍，耗时增加100倍。
洗牌算法时间复杂度为O(n)，归并排序时间复杂度O(nlogn)。
为了测试方便，将测试代码的一部分写入了sort方法里，完整的程序如下：
import random
import time
# random、numpy.random模块都有shuffle方法，这里顺便自己实现一下
class Shuffle:
@staticmethod
def knuthShuffle(a):
for i in range(0, len(a)): # 从左到右遍历数组
r=random.randint(0,i) # 生成一个0-i之间的随机数
a[i], a[r] = a[r], a[i] # 交换
class Sort:
def sort(self, a):
pass
@staticmethod
def less(small, big):
return small < big
@staticmethod
def exch(a, i, j):
a[i], a[j] = a[j], a[i]
def isSorted(self, a):
for i in range(1,len(a)):
if self.less(a[i], a[i-1]):
return False
return True
class Insertion(Sort):
def sort(self, a):
for i in range(1,len(a)):
for j in range(i,0,-1):
if self.less(a[j],a[j-1]):
self.exch(a,j,j-1)
else:
break
class Merge(Sort):
__aux = None
def sort(self, a):
self.__aux = list(a) # 创建辅助数组
l1, l2, l3, l4 = list(a), list(a), list(a), list(a)
start = time.time()
self.__sort_by_recurse(l1, 0, len(l1) - 1)
end = time.time()
print("Merge sort by recurse:",end - start,l1)
start = time.time()
self.__sort_by_loop(l2)
end = time.time()
print("Merge sort by loop:",end - start,l2)
start = time.time()
self.__merge_with_insertion(l3)
end = time.time()
print("Merge sort with insertion:",end - start,l3)
start = time.time()
self.__insertion_sort(l4)
end = time.time()
print("Insertion sort by recurse:",end - start,l4)
def __sort_by_recurse(self,a,lo,hi): # 使用递归进行自顶向下归并
if hi <= lo:
return
mid=int((hi+lo)/2)
self.__sort_by_recurse(a,lo,mid)
self.__sort_by_recurse(a,mid+1,hi)
self.__merge(a,lo,mid,hi)
def __sort_by_loop(self,a): # 使用循环，自底向上归并
sz=1
while sz<len(a):
for lo in range(0,len(a)-sz,sz+sz):
self.__merge(a,lo,lo+sz-1,min(lo+sz+sz-1,len(a)-1))
sz += sz
def __merge_with_insertion(self,a): # 对较小的子数组使用插入排序，从而减少归并次数，优化排序算法
sz=min_merge_sz=10 # 归并子数组的最小长度
for i in range(0,len(a),min_merge_sz):
a[i:min(i + min_merge_sz, len(a))] = self.__insertion_sort(a[i:min(i+min_merge_sz, len(a))]) # 对长度小于min_merge_sz的子数组使用插入排序
while sz < len(a):
for lo in range(0, len(a) - sz, sz + sz):
self.__merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, len(a) - 1))
sz += sz
def __merge(self,a,lo,mid,hi):
i=lo
j=mid+1
self.__aux[lo:hi+1]=a[lo:hi+1] #将a[lo..hi] 复制给aux[lo..hi]
for k in range(lo,hi+1):
if i > mid:
a[k] = self.__aux[j]
j+=1
elif j > hi:
a[k] = self.__aux[i]
i+=1
elif self.less(self.__aux[j],self.__aux[i]):
a[k] = self.__aux[j]
j+=1
else:
a[k] = self.__aux[i]
i+=1
def __insertion_sort(self, a):
for i in range(1, len(a)):
for j in range(i, 0, -1):
if self.less(a[j], a[j - 1]):
self.exch(a, j, j - 1)
else:
break
return a
l = [i for i in range(10000)] # 生成一个0-9999的列表
start = time.time()
Shuffle.knuthShuffle(l) # 洗牌,类内定义了static方法，不用实例化也可以调用
end = time.time()
print("Shuffling time:",end - start,l)
mergesort=Merge()
mergesort.sort(l)