归并排序--算法笔记

二路归并

原理：将序列两两分组，将序列归并为n/2个组，组内单独排序。然后再将这些组两两归并，组内再单独排序。以此类推，直到只剩下一个组为止。

递归实现：

const int maxn = 100;
//将数组A的[L1,R1]与[L2,R2]区间合并为有序区间（此处L2即为R1+1）
void merge(int A[],int L1,int R1,int L2,int R2){
	int i = L1,j=L2;
	int temp[maxn],index = 0;//temp临时存放合并后的数组，index为其下标
	while(i <= R1 && j <= R2){
		if(A[i]<=A[j]){
			temp[index++] = A[i++];// 如果A[i]<=A[j],将A[i]加入序列temp 
		}else{
			temp[index++] = A[j++];
		}
	} 
	while(i<=R1) temp[index++] = A[i++];
	while(j<=R2) temp[index++] = A[j++];
	for(i=0;i<index;i++){
		A[L1+i] = temp[i];
	}
} 
//将array数组当前区间[left,right]
void mergeSort(int A[],int left,int right){
	if(left<right){
		int mid = (left+right)/2;//取中点 
		mergeSort(A,left,mid);//递归，将左子区间[left,mid]归并排序 
		mergeSort(A,mid+1,right);//递归，将右子区间[mid+1,right]归并排序 
		merge(A,left,mid,mid+1,right);//将左子区间和右子区间合并 
	}
}