基本思想
将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到n/2个长度为2或1的有序子序列；再两两合并，直到得到一个长度为n的有序序列时结束。
解题之法
template <class T>
void Merge (T A[], int i1, int i2, int j1, int j2){
// i1, j1 是子序列1的上、下界，i2， j2是子序列2的上下界
T *temp = new T[j2 - i1 + 1]; //分配能存放两个子序列的临时数组
int i = i1, j = i2, k = 0; // i,j是两个子序列的游动指针，k是temp的游动指针
while (i <= j1 && j <= j2) { // 若两个子序列都不空，则循环
if (A[i] <= A[j]) // 将A[i] 和A[j]中较小的存入temp[k]
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
while (i <= j1) // 若第一个子序列中还有剩余的就存入temp
temp[k++] = A[i++];
while (j <= j2) // 若第二个子序列中还有剩余的就存入temp
temp[k++] = A[j++];
for (i = 0; i < k; i++) // 将临时数组中的元素倒回A
A[i1++] = temp[i];
delete[] temp;
}
template <class T>
void MergeSort (T A[], int n){
int i1, j1, i2, j2; // i1, j1是子序列1的下上界，i2，j2是子序列2的下上界
int size = 1; // 子序列中元素个数，初始化为1
while (size < n){
i1 = 0;
while (i1+size < n){ // 若i1 + size < n,则存在2个子序列，需要两两合并
i2 = i1 + size; // 确定子序列2的下界
j1 = i2 - 1; // 确定子序列1的上界
if (i2 + size - 1 > n -1)
j2 = n - 1; // 若第2个子序列中不足size个元素，则置子序列2的上界j2 = n - 1
else
j2 = i2 + size - 1; // 否则有size个，置 j2 = i2 + size - 1
Merge(A, i1, j1, i2, j2); // 合并相邻2个子序列
i1 = j2 + 1; // 确定下一次合并第一个子序列的下界
}
size *= 2; // 元素个数扩大一倍
}
}
