归并排序

整个归并排序需要进行$O(log_2n)$次每一次的归并时间复杂度为$O(n)$
所以一共的时间复杂度也为$O(nlog_2n)$
归并排序是一种稳定的排序方法

void Merge(SqList &L,int low,int mid,int high){//low=1 high=n表长 
	int i,j,k;
	SqList B;//辅助顺序表B 
	B.data=new ElemType[MAXSIZE];
	for(k=low;k<=high;k++) B.data[k]=L.data[k];//将L中所有的元素都复制到B中 
	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
		if(B.data[i]<=B.data[j]) L.data[k]=B.data[i++];//将B划分为左右半区 从各自半区第一个互相比较 
		else L.data[k]=B.data[j++];//较小的插入到L中 然后后移继续比较大小 直到i超过mid或者j超过high 
	}
	while(i<=mid) L.data[k++]=B.data[i++];//j越界了i还未遍历完 表示左边区剩下的都是大的 
	while(j<=high)  L.data[k++]=B.data[j++];//i越界了j还未遍历完 表示右半区剩下的都是大的 
	//这两个while循环只会有一个会执行 
}
bool MergeSort(SqList &L,int low,int high){
	if(low<high){
		int mid=(low+high)/2;
		MergeSort(L,low,mid);//左半区递归 
		MergeSort(L,mid+1,high);//右半区递归 
		Merge(L,low,mid,high);
	}
	return 1;
}