基本思想
核心思想是“分治法”。 将序列看成nge有序的子序列，每个序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列，然后再两两归并······这样重复下去，直到得到一个长度为n的有序序列，这种排序方法叫做2-路归并算法。依次类推，还有3-路归并排序等等。
如何有效的将两个有序序列合并
从比较两个序列的第一个元素，谁比较小就取谁，取了之后删除这个元素，然后继续比较；如果有一个序列为空，直接把不为空的序列依次取出即可。
python实现
# 合并两个有序序列
def merge(left, right):
l, r = 0, 0
# 存储取出的元素
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
# 有序列为空的时候，直接把不为空的序列拼接
result += left[l:]
result += right[r:]
return result
# 将序列分为两组，如果都有序，则可以直接合并，不然继续分成两组
def mergeSort(alist):
if len(alist) <= 1:
return alist
mid = len(alist) // 2
# 左边有序
left = mergeSort(alist[:mid])
# 右边有序
right = mergeSort(alist[mid:])
# 将两个有序序列合并
return merge(left, right)
if __name__ == '__main__':
a = [29, 10, 28, 17, 19, 14, 20]
result = mergeSort(a)
print(result) # [10, 14, 17, 19, 20, 28, 29]
