排序算法（四）：归并排序
归并排序是通过分治的方式，将待排序集合拆分为多个子集合，对子集合排序后，合并子集合成为较大的子集合，不断合并最终完成整个集合的排序。
以下所讲归并都是指二路归并：
之前的冒泡、选择和插入排序都是维持一个待排序集合和一个已排序集合，在每次的迭代过程中从待排序集合中移动一个元素到已排序集合中，通过不断的迭代来完成排序，所以需要进行的迭代次数一般都是级别。而归并排序则是每轮迭代消除半数的待排序子集合，所以需要进行的迭代次数为
级别。
算法过程
以递增排序为例
- 将集合尽量拆分为两个元素个数相等的子集合，并对子集合继续拆分，直到拆分后的子集合元素个数为 1；
- 将相邻子集合进行合并成为有序集合，若集合个数为奇数则最末尾集合不参与此次合并；
- 重复步骤 2，直到集合个数为 1
合并操作
设有两个已排序集合 和
，集合中元素个数分别为
和
，则合并
和
的操作为：
- 声明一个大小为
的集合
用于存放合并后元素；
- 声明
和
两个变量分别指向两个集合中的首元素；
- 比较
- 重复步骤 3，直到
和
中一个集合的元素已全部移动到集合
合并操作示例
merge
指向集合一中首元素位置，即指向元素 1 ，
指向集合二中首元素位置，即指向元素 3。比较 1 和 3 并将元素 1 存放到临时集合中，更新
指向元素 5。比较 5 和 3 并将元素 3 存放到临时集合中，更新
指向元素 7。再次比较并将元素 5 存放到临时集合中，此时集合一中所有元素都放到了临时集合中，则将集合二中剩余所有元素添加到临时集合中。
通过以上过程可以发现，若集合一和集合二中元素个数皆是 ：
- 若集合一中最小元素，大于集合二中最大元素，则只需要比较
次即可
- 若两集合中元素呈现交叉形式，如：[1, 3, 5]、[2, 4, 6]，则需要的比较次数为
合并操作代码
def merge(arr, left, right, end):
# 声明index_1、index_2分别指向两个集合的首元素位置
# 声明temp_arr_index指向临时集合的首元素位置
index_1, index_2, temp_arr_index = left, right, left
# 比较两集合元素，选择较小的元素添加到临时集合中
while index_1 < right and index_2 <= end:
if arr[index_1] <= arr[index_2]:
temp_arr[temp_arr_index] = arr[index_1]
index_1 = index_1 + 1
else:
temp_arr[temp_arr_index] = arr[index_2]
index_2 = index_2 + 1
temp_arr_index = temp_arr_index + 1
# 集合1元素并未全部添加到临时集合，则添加剩余元素到临时集合中
while index_1 < right:
temp_arr[temp_arr_index] = arr[index_1]
index_1 = index_1 + 1
temp_arr_index = temp_arr_index + 1
# 集合2元素并未全部添加到临时集合，则添加剩余元素到临时集合中
while index_2 <= end:
temp_arr[temp_arr_index] = arr[index_2]
index_2 = index_2 + 1
temp_arr_index = temp_arr_index + 1
temp_arr_index = left
# 将临时集合中元素复制回arr集合中，即完成了两个子集合的合并
while temp_arr_index <= end:
arr[temp_arr_index] = temp_arr[temp_arr_index]
temp_arr_index = temp_arr_index + 1
算法过程示例
recursive merge sort
上图中所示为使用递归方式完成归并排序的过程。若集合只有一个元素，则该集合为有序的，所以将原始集合拆分为多个只有单个元素的子集合后，则每次合并选择的两个集合都是有序集合。然后将合并后的有序集合再进行合并，回溯执行，直到合并后的集合包含所有元素，即完成了排序。
算法递归代码
def mergeSort(arr, left, right):
if not right > left:
return
middle = left + (right - left) // 2
mergeSort(arr, left, middle) # 左半部分集合进行排序
mergeSort(arr, middle + 1, right) # 右半部分集合进行排序
merge(arr, left, middle + 1, right) #将左右子集合合并，即完成整个集合的排序
非递归实现
归并排序的思路是通过不断合并有序子集合来构成更大的有序集合，直到合并后的集合包含所有元素。
循环合并过程
non_recursive merge sort
在循环方式的归并排序中，随着集合中元素个数的增多，不断调整集合与下一个集合的间距来完成合并。
非递归代码
def non_recursive_mergeSort(arr):
global temp_arr #临时序列存储空间
temp_arr = [None] * len(arr)
gap_len = 1 #集合之间的间距
while gap_len < len(arr):
left = 0
while left + gap_len < len(arr): #判断下一个集合是否存在
right = left + gap_len
if right + gap_len - 1 < len(arr): #判断下一个集合的尾元素位置
end = right + gap_len - 1
else:
end = len(arr) - 1
merge(arr,left,right,end)
left = left + gap_len * 2
gap_len = gap_len * 2
代码分析 ：
- 第一层循环为判断停止条件，即集合之间的间距不小于原始集合的长度时排序完成。因为集合的间距以指数形式增长，所以元素个数为
的集合，迭代的次数为
级别；
- 嵌套循环作用是遍历合并相邻的两个子集合。
算法分析
归并排序是一种稳定排序算法，排序过程中，如果两个元素值相等，则不交换元素位置。对于 个元素的序列：
-
最坏情况下，当每两个待合并集合的元素大小呈现交叉形式时，需要比较的次数为两集合元素个数之和减一。即
，公式中的每一项，括号中表示两个集合合并需要进行的比较次数，即元素个数之和减一。括号后乘的系数为拆分后每一层有多少组集合。即最坏情况下的比较次数为：
-
最好情况下，当待合并的两个集合中，其中一个集合的最小元素大于另一个集合的最大元素时，需要比较的次数为其中一个集合的元素个数。即
，即最好情况下的比较次数为：
无论是最好情况或者最坏情况下，每两个集合的合并操作都需要移动全部元素到临时集合中，再从临时集合中移动回原集合中，所以归并排序中元素的移动次数为：。根据算法执行的比较次数和元素移动次数可知，算法的时间复杂度为：
。算法执行过程中，需要申请额外的序列空间来保存临时元素，所以算法的空间复杂度为
。
