归并排序法：是采用分治法的一个非常典型的应用。
分治法:
分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
#归并排序法
#1、合并的过程函数
# left 开始索引下标；m数组中间值下标；right结束索引下标
def merge(arr,left,m,right):
n1=m-left+1 #前子数组的长度
n2=right-m #后子数组的长度
#创建临时数组
L=[0]*n1
R=[0]*n2
#拷贝数据到临时数组
for i in range(0,n1): #把前子数组的元素拷贝到左边的临时数组
L[i]=arr[left+i]
for j in range(0,n2): #把后子数组的元素拷贝到右边的临时数组
R[j]=arr[m+1+j]
#归并临时数组到 arr[1..r]
#把左右临时数组的元素，按大小合并到原数组中
i=0 #初始化第一个子数组的索引
j=0 #初始化第二个子数组的索引
k=left #初始归并子数组的索引
while i < n1 and j<n2:
if L[i]<=R[j]: 【<=:是按有小到大的顺序；>=:是按由大到小的顺序】
arr[k]=L[i]
i+=1
else:
arr[k]=R[j]
j+=1
k +=1
#拷贝 L[] 剩下的保留元素
#如果右边的数字元素都并入完了，左边数组还有元素，则不需要再进行比较，集中并入
while i<n1:
arr[k]=L[i]
i+=1
k+=1
#拷贝 R[]剩下 的保留元素
#如果左边的数字元素都并入完了，右边数组还有元素，则不需要再进行比较，集中并入
while j<n2:
arr[k]=R[j]
j+=1
k+=1
#2、分 的过程
#先分：一直分到单个元素后，从单个元素再合并的操作
def mergeSort(arr,left,right):
if left >= right:
return
m=int((left+right)/2)
mergeSort(arr,left,m) #递归对数列的前半部分进行分开
mergeSort(arr,m+1,right) #递归对数列的后半部分进行分开
merge(arr,left,m,right) #从分开后的单个元素开始进行合并
#测试
arr=[8,4,7,5,3,1,6,2]
n=len(arr)
mergeSort(arr,0,n-1)
print("排序后的数值")
for i in range(n):
print("%d" %arr[i])