研究僧考试考到了归并排序，当时做题的时候大概知道思路，结果没写上去，快气死了。。。下面总结一下归并排序。
原理
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕
实例
假设有一组数字：9 1 5 3 4 2 6 8 7 ，使用归并排序来排序，结果如下：
第一遍：1 9 3 5 2 4 6 8 7
第二遍：1 3 5 9 2 4 6 8 7
第三遍：1 2 3 4 5 6 8 9 7
第四遍：1 2 3 4 5 6 7 8 9
完成。先是两两一组，然后四四一组，然后大家一起一组，排序完成。
复杂度等
时间复杂度
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
空间复杂度
由前面的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
算法稳定性
在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。
比较
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
这些排序我们都应该掌握，比较都是基础的排序。