合并排序（归并排序）采用分治法（Divide and Conquer），先递归分解数组，将序列每次折半划分，再合并数组，将划分后的序列两两合并后排序。
基本方法：
1、将序列从中间位置分成左右两个序列
2、再将这两个子序列按照第1步继续二分下去，直到所有左右子序列的长度都为1
3、将合并排序的左右序列合并成一个有序序列
def Merge(left, right): # 将左右数组元素排序并合并成一个数组
temp = []
i = j = 0
while i < len(left) and j < len(right): # 将两边数组的元素进行比较，选择较小的填进临时数组，直到将一边填完
if left[i] < right[j]:
temp.append(left[i])
i += 1
else:
temp.append(right[j])
j += 1
if i == len(left): # 左侧数组已比对完，把右侧数组剩余数据全部填充到数组
for k in right[j:]:
temp.append(k)
else: # 右侧数组已比对完，把左侧数组剩余数据全部填充到数组
for h in left[i:]:
temp.append(h)
print('Merge temp:',temp)
return temp
def MergeSort(ls):
if len(ls) < 2: # 单个元素列表无需排序
return ls
middle = len(ls)//2
left = MergeSort(ls[:middle]) # 左边列表元素递归分解并排序
print('MergeSort left:',left)
right = MergeSort(ls[middle:]) # 右边列表元素递归分解并排序
print('MergeSort right:',right)
return Merge(left, right) # 左右两边分解的列表做最后合并
a = [8,4,5,7,1,3,6,2]
print('合并排序结果为:',MergeSort(a))
====================== RESTART: test.py ======================
MergeSort left: [8]
MergeSort right: [4]
Merge temp: [4, 8]
MergeSort left: [4, 8]
MergeSort left: [5]
MergeSort right: [7]
Merge temp: [5, 7]
MergeSort right: [5, 7]
Merge temp: [4, 5, 7, 8]
MergeSort left: [4, 5, 7, 8]
MergeSort left: [1]
MergeSort right: [3]
Merge temp: [1, 3]
MergeSort left: [1, 3]
MergeSort left: [6]
MergeSort right: [2]
Merge temp: [2, 6]
MergeSort right: [2, 6]
Merge temp: [1, 2, 3, 6]
MergeSort right: [1, 2, 3, 6]
Merge temp: [1, 2, 3, 4, 5, 6, 7, 8]
合并排序结果为: [1, 2, 3, 4, 5, 6, 7, 8]
