一.归并排序概述
归并排序的思想：假设初始序列有n个记录，则可看成是有n个有序的子序列，每个子序列长度为1，然后两两归并，如此重复直到序列有序为止，总共需要
向上取整躺排序，其计算方法与计算树的深度相同，第h-1层的元素个数为：n = 2^(h - 1)，即: h = + 1。所以总的时间复杂度是O(nlogn)。
二.链表的归并排序
由于链表结构的特殊性，而不能像连续空间容器(如vector)那样进行排序。因此在STL中为链表专门实现一种高效的归并排序方式，保证了时间复杂度不受链表结构的影响。
1. 数据结构的初始化
在算法中主要创建了一个大小为64的链表数组，数组的每一个元素都是一个链表，用于保存稍后归并排序的中间状态，fill变量指向最后一个包含数据的链表的后移位置，初始为0。如下图所示：
2.排序过程
每次从当前链表中取出头节点，将其与从0到fill - 1的链表进行归并，若中途遇到某个链表为空则停止归并。假设一直归并到了第i个链表（ 0 =< i <= fill - 1)，则将归并后的链表链入第i + 1个链表中,若i + 1 == fill，则fill后移（因为最有一个有元素的链表位置变了）。当全部元素依照上述方法放入后，最后将第0到fill - 1的全部链表进行归并，归并结果即所期望的排序结果。
1）插入元素5
2）插入元素3
、
2）插入元素6
因为0位置的链表为空，所以停止归并，直接将此次归并结果放入0位置
3）插入元素4
通过观察上述步骤，发现这种算法的实现完全遵循了归并排序的思想，每次拿出一个元素便相当于将每个元素看成长度为1的有序序列，再将其与位置0处的链表进行归并，位置0处的链表至多含有1个元素，因为一旦达到两个会继续向后归并，依次类推，第i个位置的链表中至多有
个元素，当将第i - 1位置链表与第i位置链表进行归并时即将两个长度为的链表进行归并，归并后若第i + 1位置处还有元素，则继续归并，否则将归并结果放入第i+1的位置。
3.算法描述
算法代码不长，相对于上述过程，只是在中间实现时加入了一个用于中转的链表carry。在理解思想后，算法应该不难看懂，此处便不再赘述