递归是个好东西，可以将一个大问题分拆成多个小问题。只要处理好每一个小问题、以及小问题合并成大问题的操作，基本就算是完成了，而程序需要写解决小问题的代码即可。但递归有时候也会有缺陷，如果递归层数控制不好、或者递归过程中生成了大量变量，容易造成栈溢出。尤其在工程中，栈溢出的问题是需要极力避免的。
常用的归并排序是使用递归的方式，将排序序列一层一层拆分成一半，完成一层的排序后再回调给上一层处理。
其实归并排序也可以使用非递归的方式，大概的流程如下：
1.循环，划分每一个片区，每一个片区从1开始；
2.将相邻的两个片区按照归并排序的方法放进buffer；
3.将从buffer复制进原片区的位置；
4.返回2直到所有片区合并完；
5.返回1，片区增大至2倍，直到片区大于数组长度。
/**
* param
* arr:数组头指针， len数组长度
*
*/
void merge_sort(int* arr, int len){
int * buff = new int[len]; //buffer空间
//片区的大小
for(int i = 1 ; i < len ; i *= 2){
//排序合并两个区
for(int j = 0 , k = i ; k < len ; j += 2*i, k += 2*i ){
int buffIndex = 0 ; //buffer 的index
//合并
for(int m = j , n = k ; ; ){
if(arr[m] <= arr[n]){
buff[buffIndex++] = arr[m++];
if(m >= k){ // 后半区copy
while(n < k + i && n < len){
buff[buffIndex++] = arr[n++];
}
break;
}
}else{
buff[buffIndex++] = arr[n++];
if(n >= k+i || n >= len){ //前半区copy
while(m < k ){
buff[buffIndex++] = arr[m++];
}
break;
}
}
}
//从buffer区copy到数组
for(int l = 0 ; l < 2*i && j + l < len; l++){
arr[j+l] = buff[l];
}
}
}
delete [] buff;
}