注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为5分钟。
前面介绍过分治策略，下面看看分治策略在排序中的一个应用——归并排序(Merge Sort)。
归并排序(Merge Sort)
归并排序就是递归算法，思路是，将需要排序的数据表持续分裂为两半，对两半分别进行归并排序。其套用递归三定律如下：
- 基本结束条件——数据表仅有1个数据项。这种情况就已经是排好序的。
- 缩小规模——将数据表分裂为相等的两半，规模减为原来的1/2。
- 调用自身——将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表。
归并排序的参考代码如下：
# 归并排序v1。
def mergeSort(alist):
# print(f'Splitting {alist}')
if len(alist) > 1: # 基本结束条件。
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
# 递归调用。
mergeSort(lefthalf) # 对左半部进行排序。
mergeSort(righthalf) # 对右半部进行排序。
i = j = k = 0
# 拉链式交错把左右半部从小到大归并到结果列表中。
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1
k += 1
# 归并左半部剩余项。
while i < len(lefthalf):
alist[k] = lefthalf[i]
i += 1
k += 1
# 归并右半部剩余项。
while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1
print(f'Merging {alist}')
l = [3, 0, 2, 9, 6, 5, 23, 15]
# 排序之后应为：[0, 2, 3, 5, 6, 9, 15, 23]。
mergeSort(l)
<<<
Merging [0, 3]
Merging [2, 9]
Merging [0, 2, 3, 9]
Merging [5, 6]
Merging [15, 23]
上述代码对于Python来说，不怎么符合Python简洁优雅的特性，也就是不那么Pythonic。
实际上，有一种更为Pythonic的代码如下：
# 归并排序v2。
def merge_sort(lst):
# 递归结束条件。
if len(lst) <= 1:
return lst
# 分解问题，并递归调用。
middle = len(lst) // 2
left = merge_sort(lst[:middle]) # 左半部排序。
right = merge_sort(lst[middle:]) # 右半部排序。
# 合并左右半部，完成排序。
merged = []
while left and right:
if left[0] <= right[0]:
merged.append(left.pop(0))
else:
merged.append(right.pop(0))
merged.extend(right if right else left)
return merged
l = [3, 0, 2, 9, 6, 5, 23, 15]
# 排序之后应为：[0, 2, 3, 5, 6, 9, 15, 23]。
print(merge_sort(l))
<<<[0, 2, 3, 5, 6, 9, 15, 23]
归并排序的算法分析
将归并排序分为两个过程进行分析：分裂和归并。
- 分裂的过程，借鉴二分查找中的分析结果，是对数复杂度，即时间复杂度为O(logn)。
- 归并的过程，相对于分裂的每个部分，其所有数据项都会被比较和放置一次，所以是线性复杂度，即其时间复杂度为O(n)。
考虑到每次分裂的部分都进行一次O(n)的数据项归并，总的时间复杂度为O(nlogn)。
最后，我们注意到算法中有两个切片操作。
但是，我们可以通过取消切片操作，改为传递两个分裂部分的起始点和终止点。更改之后仍然是可行的，只是算法可读性会稍微差一点。
我们注意到归并排序算法使用了额外1倍的存储空间用于归并。这是归并的劣势，对特大数据集进行排序时需要考虑进去。
To be continued.
