【参考代码】

void msort(int s, int t){  	if(s==t) return ;  //如果只有一个数字则返回，无须排序  	int mid=(s+t)/2;   	msort(s,mid);    //分解左序列  	msort(mid+1,t);  //分解右序列   	int i=s, j=mid+1, k=s;  //接下来合并  	  	while(i<=mid && j<=t){  	  		if(a[i]<=a[j]){  			r[k]=a[i];  			k++;  			i++;  		}else{  			r[k]=a[j];  			k++;  			j++;  		}  	}  	while(i<=mid){  //复制 左边子序列剩余   		r[k]=a[i];  		k++;  		i++;  	}  	while(i<=mid){  //复制 右边子序列剩余   		r[k]=a[j];  		k++;  		j++;  	}  	for(int i=s;i<=t;i++)  		a[i]=r[i];   }

【图解】

【合并过程】

比较a[i]和a[j]的大小，若a[i]<=a[j],则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并排序的算法我们通常用递归实现，先把排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

(adsbygoogle = window.adsbygoogle || []).push({});