归并排序算法（mergeSort）
算法思想：
Python使用函数实现：
def __merge(arrList, l, mid, r):
# 将arr[l...mid]和arr[mid + 1...r]两部分进行归并
# 一段辅助的临时空间，大小为r-l+1
aux = [None]*(r-l+1)
# 将当前要处理的arrList中的元素复制到aux中
for i in range(l, r+1):
# aux从0开始，要处理的元素从l开始，中间有个l的偏移量。
aux[i-l] = arrList[i]
# 两个指针
i = l
j = mid + 1
# 寻找arrList[k]处的元素
for k in range(l, r+1):
if i > mid:
arrList[k] = aux[j-l]
j = j + 1
elif j > r:
arrList[k] = aux[i-l]
i = i + 1
elif aux[i-l] <= aux[j-l]:
arrList[k] = aux[i-l]
i = i + 1
else:
arrList[k] = aux[j-l]
j = j + 1
def __mergeSort(arrList, l, r):
# 递归使用归并排序, 对arr[l...r]的范围进行排序
# 处理递归到底的情况
# 当l < r时，至少有两个元素需要处理
if l >= r:
return
'''
当粒度小到一定程度时，使用插入排序
if r-l < 15:
insertinSort(arrList, l, r)
return
'''
# 最小粒度拆分
# 对分开的左右两部分进行归并排序
mid = int((l+r)/2)
__mergeSort(arrList, l, mid)
__mergeSort(arrList, mid+1, r)
# 进行归并排序之后，已经保证每个部分都是有序的
# 仅当arrList[mid] > arrList[mid+1]的时候，才需要进行merge操作
# 对l->mid和mid+1->r进行merge操作
if arrList[mid] > arrList[mid+1]:
__merge(arrList, l, mid, r)
def mergeSort(arrList):
__mergeSort(arrList, 0, len(arrList)-1)
a = [4, 3, 8, 1, 2, 3, 4, 1, 5, 7]
mergeSort(a)
print(a)
# [1, 1, 2, 3, 3, 4, 4, 5, 7, 8]
自底向上的归并排序算法
算法思想：
Python使用函数实现：
