【参考代码】

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]。