​归并排序

归并排序有两种实现方式：自底向上和自顶向下

自底向上

自底向上的基本思想

第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到 个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前 个有序子文件长度为2，但最后一个子文件长度仍为1；

第2趟归并则是将第1趟归并所得到的 个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。
上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为”二路归并排序”。类似地有k(k>2)路归并排序。

代码

https://github.com/don7hao/algorithm/blob/master/sort/merge_sort.c

自顶向下

采用分治法进行自顶向下的算法设计，形式更为简洁。

自顶向下的基本思想:

设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点
mid = (low+high)/2(向下取整)
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件：子区间长度为1（一个记录自然有序）。

代码

https://github.com/don7hao/algorithm/blob/master/sort/merge_sort.c

算法分析

1.稳定性
归并排序是一种稳定的排序。

2.存储结构要求
可用顺序存储结构。也易于在链表上实现。

3.时间复杂度
对长度为n的文件，需进行lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

4.空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。