Test Windows Live Writer

template<class T>
void list_sort(list<T>& lst)
{
        if (lst.size() > 1)
        {
                list<T> carry;
                list<T> counter[64];
                int fill = 0;
                while (!lst.empty())
                {
                        carry.splice(carry.begin(), lst, lst.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]);
                lst.swap(counter[fill-1]);
        }
}

侯捷的注释是本函数采用的是快速排序的方法。我硬着头皮看了多遍硬是没看懂。网上的几篇帖子也没有说明白。直到把中间结果输出才明白，侯捷的注释是错误的，这其实是归并排序的非递归实现。
要理解这个实现，首先明确几个函数的作用：
void list::splice( iterator pos, list& lst, iterator del );
splice把lst中del所指元素删除并插入到当前list的pos位置上。
void list::merge( list &lst );
merge把lst的元素合并到当前list，参数lst的元素会被清空的。
再明确几个变量的作用：
counter[i]如不空，则存储2^i个已排好序的元素。
carry只是起中转作用。
fill标记非空counter数组元素的下标i的上界，初始时为0。
该实现可这样理解：
第9-20行是主循环，每次删除lst的首元素并将其放入counter数组列表的合适位置，直至lst为空。
第11行将lst首元素移动到carry中。
第12-18行从counter[0]开始，如当前处理的元素counter[i]非空，则归并carry与counter[i]，将结果放到carry中并把counter[i]置空，以此类推处理后一个counter元素，直到当前处理的counter元素为空。这样的处理能一直保持counter[i]的特性，即如不空则存储2^i个已排好序的元素。
第19行在适当时候更新fill值。
第21-23行将counter数组的所有元素归并，并将最终的排序结果交回给lst。
可以看一个运行实例。假设lst包含元素“7 9 0 6 10 4 0 7 5 1 0”。以下输出为从左往右每把一个lst的元素放入counter后，counter数组的存储内容。

+ 7 
[0] 7 

+ 9 
[0] 
[1] 7 9 

+ 0 
[0] 0 
[1] 7 9 

+ 6 
[0] 
[1] 
[2] 0 6 7 9 

+ 10 
[0] 10 
[1] 
[2] 0 6 7 9 

+ 4 
[0] 
[1] 4 10 
[2] 0 6 7 9 

+ 0 
[0] 0 
[1] 4 10 
[2] 0 6 7 9 

+ 7 
[0] 
[1] 
[2] 
[3] 0 0 4 6 7 7 9 10 

+ 5 
[0] 5 
[1] 
[2] 
[3] 0 0 4 6 7 7 9 10 

+ 1 
[0] 
[1] 1 5 
[2] 
[3] 0 0 4 6 7 7 9 10 

+ 0 
[0] 0 
[1] 1 5 
[2] 
[3] 0 0 4 6 7 7 9 10 

最后归并counter中的所有元素得到最终的排序结果“0 0 0 1 4 5 6 7 7 9 10”。
这其实是一个链表上的归并排序的非递归实现。好处如下：
1.使用归并排序保证了最坏的时间复杂度为O(nlog(n))。2.利用链表结构使归并的过程既只需使用常数的额外空间，时间上又很高效。3.消除了递归实现的开销。
该实现将链表数据结构和归并排序算法的优势结合得天衣无缝，令人叹服。赞！