探讨经典排序(6)---归并排序

归并:讲两个或多个有序序列合并成一个

m路归并，每一次归并都需要比对m-1个元素

以2路归并为例

int c[4]=[1,3,8,10];   
int d[5]=[5,7,9,26,75];

1. 开辟一个新空间B[9]
2. c[0]与d[0]比对，把小的元素c[0]放入B[0]
3. c[1]与d[0]比对，把小的元素c[1]放入B[1]
4. 继续上述步骤
5. 直到c已经遍历完，直接把d剩余元素放入B中

我们的归并排序实际上就是在2路归并的基础上

其核心思想就是把数组内两个有序序列归并成一个

int *B=(int *)malloc(n*sizeof(int));//辅助空间B

//A[low..mid]与A[mid+1 ... high]各自有序 ，将二者归并
void Merge(int A[],int low,int mid,int high){
	int i,j,k;
	for(k=low;k<=high;k++){
		B[k]=A[k];  //把A元素copy到B 
	}
	for(i=low,j=mid+1,k=i;i 
结论:
 
n个元素进行2路归并排序，归并趟数log2 N
每趟时间复杂度O(n)，算法时间复杂度O(Nlog2 N) 与是否有序无关