一、基本思想
对于一个待排序的序列，递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后合并这两个部分。
归并算法采用分而治之的策略：
a. 将问题分成一些小的问题然后递归求解；
b. 将分的阶段解得的各个答案“修补”到一起。
可以看到这种结构很像一棵完全二叉树，故我们可以采用递归来实现归并排序。
二、分阶段可以理解为就是递归拆分子序列的过程
由上图可知递归深度为logn，故其时间复杂度为O(logn)。
三、治阶段可以理解为就是合并相邻有序子序列的过程
我们需要将两个已经有序的子序列合并成一个有序序列。因为这两个输入子序列是有序的，所以若将输出放到第三个序列中时，则该算法可以通过对输入数据一趟排序来完成。即合并两个有序子序列的时间复杂度为O(n)。
比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，下图为对应的实现步骤。
四、代码
/* 归并排序 */
void MergeSort(int a[], int n)
{
//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
int *temp = new int[n];
sort(a, 0, n-1, temp);
delete []temp;
}
void sort(int a[], int left, int right, int temp[])
{
int mid;
if(left < right) {
mid = (left + right) / 2;
sort(a, 0, mid, temp); // 左边归并排序，使得左子序列有序
sort(a, mid + 1, right, temp); // 右边归并排序，使得右子序列有序
merge(a, left, mid + 1, right, temp); // 将两个有序子数组合并
}
}
void merge(int a[], int lPos, int rPos, int rightEnd, int temp[])
{
int leftEnd = rPos - 1; // 左边子序列的右端
int tempPos = lPos; // 临时数组的游标
int elementNum = rightEnd - lPos + 1; // 两个子序列拥有的总元素
// 合并两个子序列
while(lPos <= leftEnd && rPos <= rightEnd) {
if(a[lPos] <= a[rPos])
temp[tempPos++] = a[lPos++];
else
temp[tempPos++] = a[rPos++];
}
while(lPos <= leftEnd)
temp[tempPos++] = a[lPos++];
while(rPos <= rightEnd)
temp[tempPos++] = a[rPos++];
// 拷贝到数组a中
for(int i = 0; i < elementNum; ++i, --rightEnd)
a[rightEnd] = temp[rightEnd];
}