1 排序思想：
将待排序表R1、R2、R3、……、R（n）看成是n个长度为1的有序子表，对相邻的两个有序子表两两合并，得到每两个元素有序的表；再将长度为2的有序子表两两合并，得到每四个元素有序的表；直到得到一个长度为n的有序表。排序过程如下：
原始数据：
第1趟排序后：
第2趟排序后：
第3趟排序后：
第4趟排序后：
2 算法实现：
// 归并排序
void merge_sort(int num[], int p, int r){
if(r-p>1){
int q=(p+r)/2;
merge_sort(num, p, q);
merge_sort(num, q, r);
merge(num, p, q, r);
}
}
// 将两个列表归并的过程，这里表示将
// 列表num[]的num[p,q-1]和num[q,r-1]两段有序子表归并
void merge(int num[], int p, int q, int r){
int n1=q-p;
int n2=r-q;
// 创建两个列表，分别存储num[p,q-1]和num[q,r-1]
int *left=new int[n1];
int *right=new int[n2];
int i,j,k;
// 列表赋值
for(i=0;i<n1;i++)
left[i]=num[p+i];
for(j=0;j<n2;j++)
right[j]=num[q+j];
i=0;
j=0;
// 将两个列表left和right的内容按顺序放在num[p,r-1]
for(k=p;k<r;k++){
if(i<n1&&left[i]<=right[j]){
num[k]=left[i];
i++;
}
else if(j<n2){
num[k]=right[j];
j++;
}
}
delete []left;
delete []right;
}3 性能分析：
3.1 空间复杂度：如上代码，每一轮的归并操作使用的辅助元素数组空间长度与原始表等长，为n，而每一轮归并之后，这些辅助空间都可以释放掉，因此空间复杂度是O(n)
3.2 时间复杂度：
对于归并排序，不论原始列表排序情况如何，时间复杂度都是一样的。因为每一轮要进行的比较次数为n，赋值操作次数为2n
要进行logn轮归并操作，则时间复杂度是O(nlogn)
3.3 稳定性：稳定
