常用排序算法递归篇之归并排序
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
归并排序的实现描述：
1、首先把待排序数组分成左数组和右数组两部分；
2、分别对左数组和右数组进行迭代排序（当左数组和右数组的元素个数小于等于1个时迭代结束）；
3、然后将左数组和右数组进行合并，那么生成的整个数组就是有序的。
当左数组或者右数组的元素个数小于等于1个时，即可认为数组本身就是有序的，然后对有序的数组再进行合并，那么合并之后的数组还是有序的。具体实现代码如下：
void merge_sort(int *array, int length){ if (NULL == array || 0 == length) { return; } _merge_sort(array, 0, length - 1);}void _merge_sort(int *array, int start, int end){ if (start >= end) { return; } int middle = (start + end) / 2; _merge_sort(array, start, middle); _merge_sort(array, middle + 1, end); _merge_data(array, start, middle, end);}//合并数据array[start...middle]和数据array[middle+1...end] void _merge_data(int *array, int start, int middle, int end){ int i, j, k; int len = end - start + 1; int *arr = (int *)malloc(len * sizeof(int)); //把数据array[start...end]拷贝到数组arr memcpy(arr, array + start, len * sizeof(int)); i = 0; //arr[0]相当于array[start] j = middle - start + 1; //arr[middle - start + 1]相当于array[middle + 1] k = start; while (i <= middle - start && j <= len - 1) { if (arr[i] >= arr[j]) { array[k++] = arr[j++]; } else { array[k++] = arr[i++]; } } while (i <= middle - start) { array[k++] = arr[i++]; } while (j < len - 1) { array[k++] = arr[j++]; } free(arr); return;}快速排序和归并排序的异同点总结：
相同点：都是递归排序
不同点：快速排序是先分类再递归，归并排序是先递归再合并。
从归并排序的递归过程中可以看出，就是不停地把数组拆分成左右元素个数相同（最多相差一个元素）的两个子数组，直到子数组只有一个元素时才返回开始合并。我们可以反过来想一想，是否可以不利用递归的方法拆分数组。具体拆分、合并方法如下：
第一轮：子数组的长度为1，左数组是array[0]，右数组是array[1]，然后合并左右数组；左数组是array[2]，右数组是array[3]，然后合并左右数组；。。。
第二轮：子数组的长度为2，左数组是array[0]、array[1]，右数组是array[2]、array[3]，然后合并左右数组；。。。
第N轮：子数组的长度为2^(N-1)，左数组是array[0...2^(N-1)-1]，右数组是array[2^(N-1)...length-1]，然后合并左右数组；。。。
方法总结：首先将数组的每个元素看成是长度为1的有序子数组，然后将这些有序子数组两两合并成长度为2的有序子数组，然后再两两合并...直至合并成长度为length的有序数组。具体实现代码如下：
void merge_sort(int *array, int length){ if (NULL == array || 0 == length) { return; } int start = 0; //起始下标 int end =0; //结束下标 int len = 0; //子序列长度 len = 1; //将序列每个元素看成是长度为1的子序列 while (len < length) { start = 0; //从start开始计算，至少存在2个子序列没有合并时则继续合并 while (len + start < length) { end = start + len * 2 - 1; if (end >= length) { end = length - 1; } if (_merge_data(array, start, start + len - 1, end)) //合并失败 { return; } start = end + 1; } len *= 2; }}