原理
归并排序是利用分治思想的经典算法。其时间复杂度为 O(nlog2n)，空间复杂度为 O(n)。
它的过程严格遵循分治思想：
如果待排序列的长度小于等于 1，则结束排序。
否则将序列平分为两半，按相同方法递归地排序两个子序列。
将两个排完序的子序列合并成一个有序序列。
伪代码
var tmp= 临时数组的头指针;
function merge_sort(beg: 头指针, end: 尾后指针){
// 边界处理
var size: 数组长度 = end-beg;
if(size<=1) return;
// 递归排序
var mid: 中间位置指针 = beg+size/2;
merge_sort(beg, mid);
merge_sort(mid, end);
// 合并序列
var b1: 左半序列头指针 = beg,
b2: 右半序列头指针 = mid,
now: 临时数组头指针 = tmp,
have1: 左半序列是否还有元素 = true,
have2: 右半序列是否还有元素 = true;
while(have1 or have2){
if(have1 and (have2==false or *b1<*b2){
copy *b1 to *now;
increase b1, now;
update have1;
}
else{
copy *b2 to *now;
increase b1, now;
update have2;
}
copy [tmp, now) to [beg, end);
}
}
C++代码
int buf[MAX_SIZE]; // 临时数组
void merge_sort(int *beg, int *end){
int size= end-beg;
if(size<=1) return;
int *mid= beg+size/2;
merge_sort(beg, mid);
merge_sort(mid, end);
int *b1= beg, *b2= mid, *now= buf;
bool have1= true, have2= true;
while(have1 || have2){
if(have1 && (have2==false || *b1<*b2)){
*now++ = *b1++;
have1= b1<mid;
}
else{
*now++ = *b2++;
have2= b2<end;
}
}
memcpy(beg, buf, size*sizeof(int)); // memcpy 是拷贝字节，注意乘 sizeof
}
