list模板的定义以及一些基本成员函数的实现这里我就不赘述了，还不清楚的同学可以到网上查找相关资料或者直接查看侯捷翻译的《STL源码剖析》相应章节。我之所以写这篇笔记是因为当时看到list::sort()源码时一时没看懂，后来在VS项目里一步步跟踪数据变化发现了其中的奥秘，被其简洁高效的非递归归并排序的实现方法所震撼(侯捷在《STL源码剖析》上注释说此sort实现使用了快排，应该是弄错了),下面直接进入主题。
list::sort() 源码(摘自《STL源码剖析》)template <class T, class Alloc> void list<T, Alloc> :: sort(){ // 判断链表是否为空或者只有一个元素 if(node->next == node || link_type(node->next)->next == node){ return; } list<T, Alloc> carry; list<T, alloc> counter[64]; int fill = 0; while(!empty()){ carry.splice(carry.begin(), *this, begin()); int i = 0; while(i < fill && !counter[i].empty()){ counter[i].merge(carry); carry.swap(counter[i++]); } carry.swap(counter[i]); if(i == fill){ ++fill; } } for(int i = 1; i < fill; ++i){ counter[i].merge(counter[i-1]); } swap(counter[fill-1]); }
以上源码咋一看并没有发现元素大小比较的地方，但仔细一看便发现其使用了list的merge成员函数，这个函数功能是合并两个非减有序链表为一个非减有序链表，结果为调用该函数的对象。显然，sort函数的实现使用了归并排序。为了能在vs下调试跟踪数据变化，我新建了一个list.sort()的等价外部实现函数。
list.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]); }
算法的巧妙之处在于外层while循环下counter链表数组的维护，下面我们就用例子a(8, 6, 520, 27, 124, 214, 688, 12, 36 )来跟踪counter的变化。事先约定，null表示list不含元素，下面所说的第i次循环之后均指外层while的。a的元素个数为9，归并层次最多到达第4层，故counter[3]之后的就不显示了, 它们的值均为null。
第i次循环之后counter[0]counter[1]counter[2]counter[3]0 8 null null null
1 null 6,8 null null
2 520 6.8 null null
3 null null 6,8,27,520 null
4 124 null 6,8,27,520 null
5 null 124,214 6,8,27,520 null
6 688 124,214 6,8,27,520 null
7 null null null 6,8,12,27,124,214,520,688
8 36 null null 6,8,12,27,124,214,520,688
前3次循环的具体运行过程如下：
第0次外层循环，carry取得a列表头元素8，i == fill == 0 无法进入内层循环，之后carry与counter[0]交换，counter[0] 变为8， fill变为1；