前言 归并排序是所有常用内部排序算法中稳定性最好的,无论是平均时间复杂度、最坏时间复杂度还是最好时间复杂度,其时间复杂度都是O(nlogn)。由于这个特性,在需要考虑排序稳定性的情况下,归并排序是所有优化算法(直接插入排序、冒泡排序和简单选择排序)使用最多的。其实归并排序算法的思想很简单:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每一个子序列的长度都是1,然后把这些子序列两两归并,得到 ⌈n/2⌉ ( ⌈x⌉ 表示不小于 x 的最小整数)个长度为2或者1的有序子序列;再两两归并,……,如此重复,直至得…