list::sort源码对比（侯捷老师源码剖析和c++11中当前使用的库中的实现）

首先看一下侯捷老师《STL源码剖析》中的源码

// list 不能使用STL 算法 sort()，必须使用自己的 sort() member function，
// 因为STL算法sort() 只接受RamdonAccessIterator.
template 
void list::sort() {
    // 如果为空链表或只有一个元素的链表，则什么也不做
    if (node->next == node || link_type(node->next)->next == node) return;
    
    // 一些新的 lists，做为中介数据存放区
    list carry;
    list 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]);
}

在书中侯捷老师说是使用的快速排序，由于自己的水平有限，不妄作定义，看了分析过程，各位大佬可能会自自有各自理解。

先看一下代码中用到的函数：

1. splice：主要拼接作用，有以下重载版本

	1. splice(itreator position, list &x)//将x拼接到指定Position位置之前，Splice为成员函数，所以默认对*this进行操作,该函数x必须不同于*this
	2. splice(iterator position, list &, iterator i)//将i所指元素接合于position位置之前。position和i可指向同一个list
	3. splice(iterator position, list &, iterator first, iterator last)//将[fisrt, last)范围内的元素接合于position位置之前

2. merge

	merge(list &x)//将*this和x进行合并，两个list都必须确保进行了递增排序

3. swap

	//交换两个对象的值
	template 
	void swap(T &x, T &y){
		T temp = x;
		x = y;
		y = temp;
	}

通过一个例子来进行说明：
假设现在需要对lsit = [0, 2, 99, 3, 4]进行排序
第一步：fill = 0, carry链表通过splice后为{0}
	此时i = 0，对于while(i < fill && !counter[i].empty()), i == fill所以为假
	将carry和counter[i](即count[0])进行交换，所以此时counter[0]为{0} ，carry为null
	最后一个if (i == fill) ++fill;满足条件，所以fill变为1，进行下一轮循环
第二步：fill = 1, carry通过splice后为{2}
	此时i = 0, while(i < fill && !counter[i].empty()), （i = 0） < (fill = 1)，并且由第一步知counert[i](即counter[0])不为空，条件为真，进入内部while循环
	将carry合并到counter[0]上后，carry为空，counter0]为{0，2}
	再通过swap将carry和counter0]进行交换，所以此时carry为{0,2},counter[0]为空,并且伴随将i值变为1
	此时内层的while循环条件不满足，跳出循环，执行carry和counter[1]的交换，所以此时
	carry为空，counter[0]为空，counter[1]为{0，2}.
	此时(i = 1) == (fill = 1),所以fill变为2.
	到这一步，counter数组的样子如下：
	counter[0]:  {}
	counter[1]:  {0,2}
	counter[2]:  {}
	....
	counter[64]: {}
第三步：fill  = 2,carry = {99}，i = 0
	while(i < fill && !counter[i].empty())为假 因为counter[0]为空
	carry和counter[0]交换，carry为空，counert[0]:{99}
第四步：fill = 2, carry = {3}, i = 0
	while(i < fill && !counter[i].empty())为真
		counter0]为{3，99}, carry为空；
		counter[0]为空， carry为{3，99}, i = 1
		counter[1]为{0，2，3，99}, carry为空
		counter[1]为空， carry为{0，2，3，99},i = 2
	counter[2] = {0,2,3,99},carry为空， (i = 2) == (fill = 2)，所以fill = 3
	到此：
		counter[0]:{}
		counter[1]:{}
		counter[2]:{0,2,3,99}
		....
		counter[64]:{}
第五步：fill = 3, carry :{4},i = 0
	while(i < fill && !counter[i].empty())为假，counter[0-1]均为空
	counter[0] = {4}, carry:空
	此时进行下一轮循环判断while (!empty())为假，跳出循环，此时counter和carry的情况为

carry : {}
counter[0]:{4}
counter[1]:{}
counter[2]:{0,2,3,99}
counter[3]:{}
...
counter[64]:{}
fill = 3
随后执行
for (int i = 1; i < fill; ++i)
   	 counter[i].merge(counter[i-1]);
最后合并后counter[2]:{0,2,3,4,99}
最后经过交换，*this即为{0，2，3，4，99}完成排序

上述即为一个简单的排序过程，描述有点口水，从该过程看着不像是快排，有点归并的意思，各位大佬觉得呢？
最后再来看看c++11后list类库中的sort代码：

template
void list<_Tp, _Alloc>::sort() {
      // Do nothing if the list has length 0 or 1.
      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
	        && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) {
            list __carry;
            list __tmp[64];
            list * __fill = __tmp;
            list * __counter;
        __try {
            do {
                __carry.splice(__carry.begin(), *this, begin());

                for(__counter = __tmp;
                    __counter != __fill && !__counter->empty();
                    ++__counter) {
                    __counter->merge(__carry);
                    __carry.swap(*__counter);
                }
                __carry.swap(*__counter);
                if (__counter == __fill) ++__fill;

            }while ( !empty() );

            for (__counter = __tmp + 1; __counter != __fill; ++__counter)
                __counter->merge(*(__counter - 1));
            swap( *(__fill - 1) );

        }__catch(...){
            this->splice(this->end(), __carry);
            for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
            this->splice(this->end(), __tmp[__i]);
            __throw_exception_again;    //一个宏定义相当于throw抛出异常
        }
    }
}

整体思想没有改变，只是代码结构方面进行重新设计！
最后感谢各位，时间紧迫，写的急，如有错误，还请指出！

参考资料：侯捷《STL源码剖析》