第1次外层循环， carry取得a列表头元素6，counter[0]不为空故进入内层循环，合并carry和counter[0]，内层一次循环之后counter[0]变为null， carry变为(6,8), i == fill == 1退出内层循环。然后carry与counter[1]交换，最后counter[1]变为(6, 8), fill 变为2；
第2次外层循环， carry取得a列表头元素520，counter[0]为空无法进入内层循环，之后carry与counter[0]交换，counter[0] 变为520， fill的值不变；
第3次外层循环，carry取得a列表头元素27，进入内层while循环，先是发现counter[0]不为空，故与其合并，合并之后carry变为(27, 520), counter[0]变为null，然后进入下一次内层循环发现counter[1]不为空，故与其合并，合并之后carry变为(6,8,27,520)， counter[1]变为null，i == fill == 2退出内层循环。最后carry与counter[2]互换，counter[2]变为(6,8,27,520)，fill变为3.
之后的循环过程类似，最后将counter[0]至counter[8]的结果合并即为结果。此算法的时间复杂度为O(N*logN)，空间复杂度为O(N).
总结传统归并排序使用先二分后调用递归函数的步骤，应用对象主要是普通数组和vector数组，这两者的共同点在于可以在O(1)的时间内找到中点。但分析list数据结构可知，寻找其中点需要O(N)复杂度，故不大适合使用传统归并排序的思想。后来不知哪位牛人想到了利用二进制的进位思想，结合一个list数组保存各个归并层次的结果，最终实现了非递归版的归并排序，此想法也可以用在普通数组和vector数组上，具体实现以后有时间再写。
附调试完整代码#include <iostream> #include <list> using namespace std; // list<T>.sort()等价外部实现，用到了归并排序的算法思想 void sortList(list<int> &a) { if(a.size() <= 1){ return; } list<int> carry; // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果 list<int> counter[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0 int fill = 0; // 表示当前最大归并排序的层次，while循环之后fill变成log2(a.size()) while (!a.empty()) { carry.splice(carry.begin(), a, a.begin()); // 将链表a中的第一个元素移动至carry开头 int i = 0; // 从小往大不断合并非空归并层次直至遇到空层或者到达当前最大归并层次 while (i < fill && !counter[i].empty()) { counter[i].merge(carry); // 链表合并，结果链表是有序的，必须保证合并前两个链表是有序的 carry.swap(counter[i++]); // 链表元素互换 } carry.swap(counter[i]); if (i == fill) { // i到达当前最大归并层次，说明得增加一层 ++fill; } } for (int i = 1; i < fill; ++i) { // 将所有归并层次的结果合并得到最终结果counter[fill - 1] counter[i].merge(counter[i - 1]); } a.swap(counter[fill - 1]); } int main() { list<int> test; test.push_back(8); test.push_back(6); test.push_back(520); test.push_back(27); test.push_back(124); test.push_back(214); test.push_back(688); test.push_back(12); test.push_back(36); cout << "排序前" << endl; for (auto i = test.begin(); i != test.end(); i++) { cout << *i << " "; } cout << endl << "排序后：" << endl; sortList(test); for (auto i = test.begin(); i != test.end(); i++) { cout << *i << " "; } cout << endl; return 0; }