1. 归并排序原理：有长度为n的子序列a[n]，可以将其看做n个长度为1的子序列，将相邻子序列两两归并后子序列数量减少一半，再对子序列进行两两归并，数量又减少一般，重复直到得到一个长度为n的子序列
2. 实现归并操作的代码如下：
/*array[s…m]和array[m+1…t]均已各自有序，合并使得array[s…t]有序*/ void Merge(int s, int m, int t, int *array) { int temp[t-s+1];/*设临时数组存放排序后的元素*/ int i=s, j=m+1, k=0; while(i<=m && j<=t) { if(array[i] < array[j]) temp[k++] = array[i++]; else temp[k++] = array[j++]; } while(i<=m) temp[k++] = array[i++]; while(j<=t) temp[k++] = array[j++]; for(i=s, k=0; i<=t && k<=t-s; i++, k++) /*将临时数组里的元素复制到原数组*/ { array[i] = temp[k]; } }
3. 递归调用代码如下：
void MSort (int s, int t, int *array) /*递归调用*/ { if(s == t) return ; int m = (s+t)/2; /*设置中间数*/ MSort(s, m, array); /*左边序列有序*/ MSort(m+1, t, array); /*右边序列有序*/ Merge(s, m, t, array); /*将左右有序序列归并*/ } void MergeSort1(int n, int *array) { MSort(0, n-1, array); }
4. 归并排序非递归调用的实现
由于大量引入递归造成时间和空间上性能的损耗，所以我们考虑引入迭代来代替递归，效率必然要高于递归，如下：
void MergeSort2(int n, int *array) { int k, i; for (k=1; 2*k<n; k *= 2) /*设置每段待归并的有序序列的长度：1,2,4,8,16……*/ { for (i=0; i+k-1<n; i += 2*k)/*考虑待归并的左右两段序列，[i+k-1]是左序列末尾元素下标*/ { /*[end=i+2*k-1]是右序列末尾元素下标,end不应该超过n-1*/ int end=i+2*k-1; if(end > n-1) end = n-1; Merge(i, i+k-1, end, array); } } }
原文：http://www.cnblogs.com/lifan/p/3718489.html