stl中的list 是双向链表结构，最近用到其中的sort方法，文档中有这么两段：
Sorts *this according to
operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements.
[6] The number of comparisons is approximately
N log N, where N is the
list's size.
-》[6] The
sort algorithm works only for
random access iterators. In principle, however, it would be possible to write a sort algorithm that also accepted
bidirectional iterators. Even if there were such a version of
sort, it would still be useful for
list to have a sort member function. That is,
sort is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.
可以看出 stl中的sort算法一般只支持 随机访问的结构，对于list来说，一般使用它自己的sort成员函数，并且时间复杂度在nlogn。
由于对链表结构的排序比较感兴趣，回头在网上搜索了一下list内部的sort算法分析，由源码分析可以看出list内部的sort函数，实际上是通过链表方式实现的非递归的mergesort，时间复杂度在nlogn,并且空间复杂度为O(1),下面贴两篇分析的文章：
---------------------------------------
stl中的list被实现为环状的双向链表，设置一个“哨”node作为end( )。list没有使用标准sort算法，而是实现自身的sort，本质上是mergesort（侯捷解释的是错的），但是采用了一个特殊的形式：
普通的mergesort直接将待排序的序列一分为二，然后各自递归调用mergesort，再使用Merge算法用O(n)的时间将已排完序的两个子序列归并，从而总时间效率为n*lg(n)。(mergesort是很好的排序算法，绝对时间很小，n*lg(n)之前的系数也很小，但是在内存中的排序算法中并不常见，我想可能主要还是因为耗空间太多，也是O(n))
list_sort所使用的mergesort形式上大不一样：将前两个元素归并，再将后两个元素归并，归并这两个小子序列成为4个元素的有序子序列；重复这一过程，得到8个元素的有序子序列，16个的，32个的。。。，直到全部处理完。主要调用了swap和merge函数，而这些又依赖于内部实现的transfer函数(其时间代价为O(1))。该mergesort算法时间代价亦为n*lg(n)，计算起来比较复杂。list_sort中预留了64个temp_list，所以最多可以处理2^64-1个元素的序列，这应该足够了：）
为何list不使用普通的mergesort呢?这比较好理解，因为每次找到中间元素再一分为二的代价实在太大了，不适合list这种非RandomAccess的容器。
为何list不使用标准sort算法呢(标准sort要求RandomAccessIterator)？至少普通的quicksort我觉得应该是可以的，具体原因等查查标准算法实现再来说了。
下面把gcc4.02中list_sort的实现贴上：
template<typename _Tp, typename _Alloc>
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[0];
list * __counter;
do
{
__carry.splice(__carry.begin(), *this, begin());
for(__counter = &__tmp[0];
__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) );
}
}
--------------------------------------------------------
list::sort() 这个函数使用了非常巧妙的算法，来对list中的元素进行排序，在某些书上看到，指出该算法是快速排序，个人认为应该是归并排序更为确切。。所以提供了以下测试代码以观察整个排序过程。
#include <iostream>
#include <list>
#include <iomanip>
using namespace std;
//the max value is 64
const int SCALE=10;
template <typename T>
void print_dbg(list<T>& iList, list<T>& carry, list<T>* counter)
{
typename list<T>::iterator it2;
cout<<"list: ";
it2=iList.begin();
while(it2!=iList.end())
{
cout<<setw(3)<<*it2++;
}
cout<<endl;
cout<<"carry: ";
it2=carry.begin();
while(it2!=carry.end())
{
cout<<setw(3)<<*it2++;
}
cout<<endl;
for(int i=0; i<SCALE; ++i)
{
if(!counter[i].empty())
{
cout<<"counter["<<i<<"]: ";
it2=counter[i].begin();
while(it2!=counter[i].end())
{
cout<<setw(3)<<*it2++;
}
cout<<endl;
}
}
cout<<endl<<endl;
}
template <typename T>
void LSort(list<T> &iList)
{
if(iList.size()<= 1)
{
return;
}
list<T> carry;
list<T> counter[64];
int fill = 0;
typename list<T>::iterator it;
while (!iList.empty())
{
carry.splice(carry.begin(), iList, iList.begin());
print_dbg(iList, carry, counter);
int i = 0;
while(i < fill && !counter[i].empty())
{
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
print_dbg(iList, carry, counter);
if (i == fill)
{
++fill;
}
cout<<endl<<endl<<endl;
}
for (int i = 1; i < fill; ++i)
{
counter[i].merge(counter[i-1]);
}
print_dbg(iList, carry, counter);
iList.swap(counter[fill-1]);
}
int main()
{
int arr[]={22,43,1,32,43,3,65,8,56,98,4,23,87,94,37,77,35,36,0};
list<int> iList(arr,arr+sizeof(arr)/sizeof(int));
list<int>::iterator it;
LSort(iList);
cout<<"Complete! After sort: "<<endl;
it=iList.begin();
while(it!=iList.end())
{
cout<<setw(3)<<*it++;
}
cout<<endl<<endl;
system("pause");
return 0;
}
通过函数print_dbg()打印所有中间链表的内容，在以上数组的输入时，可以得到以下输出：
list: 43 1 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36
carry: 22
list: 43 1 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36
carry:
counter[0]: 22
list: 1 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry: 43
counter[0]: 22
list: 1 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[1]: 22 43
list: 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry: 1
counter[1]: 22 43
list: 32 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[0]: 1
counter[1]: 22 43
list: 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry: 32
counter[0]: 1
counter[1]: 22 43
list: 43 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[2]: 1 22 32 43
list: 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry: 43
counter[2]: 1 22 32 43
list: 3 65 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[0]: 43
counter[2]: 1 22 32 43
list: 65 8 56 98 4 23 87 94 37 77 35 36 0
carry: 3
counter[0]: 43
counter[2]: 1 22 32 43
list: 65 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[1]: 3 43
counter[2]: 1 22 32 43
list: 8 56 98 4 23 87 94 37 77 35 36 0
carry: 65
counter[1]: 3 43
counter[2]: 1 22 32 43
list: 8 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[0]: 65
counter[1]: 3 43
counter[2]: 1 22 32 43
list: 56 98 4 23 87 94 37 77 35 36 0
carry: 8
counter[0]: 65
counter[1]: 3 43
counter[2]: 1 22 32 43
list: 56 98 4 23 87 94 37 77 35 36 0
carry:
counter[3]: 1 3 8 22 32 43 43 65
list: 98 4 23 87 94 37 77 35 36 0
carry: 56
counter[3]: 1 3 8 22 32 43 43 65
list: 98 4 23 87 94 37 77 35 36 0
carry:
counter[0]: 56
counter[3]: 1 3 8 22 32 43 43 65
list: 4 23 87 94 37 77 35 36 0
carry: 98
counter[0]: 56
counter[3]: 1 3 8 22 32 43 43 6
list: 4 23 87 94 37 77 35 36 0
carry:
counter[1]: 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 23 87 94 37 77 35 36 0
carry: 4
counter[1]: 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 23 87 94 37 77 35 36 0
carry:
counter[0]: 4
counter[1]: 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 87 94 37 77 35 36 0
carry: 23
counter[0]: 4
counter[1]: 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 87 94 37 77 35 36 0
carry:
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 94 37 77 35 36 0
carry: 87
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 94 37 77 35 36 0
carry:
counter[0]: 87
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 37 77 35 36 0
carry: 94
counter[0]: 87
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 37 77 35 36 0
carry:
counter[1]: 87 94
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 77 35 36 0
carry: 37
counter[1]: 87 94
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 77 35 36 0
carry:
counter[0]: 37
counter[1]: 87 94
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 35 36 0
carry: 77
counter[0]: 37
counter[1]: 87 94
counter[2]: 4 23 56 98
counter[3]: 1 3 8 22 32 43 43 65
list: 35 36 0
carry:
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list: 36 0
carry: 35
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list: 36 0
carry:
counter[0]: 35
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list: 0
carry: 36
counter[0]: 35
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list: 0
carry:
counter[1]: 35 36
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list:
carry: 0
counter[1]: 35 36
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list:
carry:
counter[0]: 0
counter[1]: 35 36
counter[4]: 1 3 4 8 22 23 32 37 43 43 56 65 77 87 94
list:
carry:
counter[4]: 0 1 3 4 8 22 23 32 35 36 37 43 43 56 65
Complete! After sort:
0 1 3 4 8 22 23 32 35 36 37 43 43 56 65 77 87 94 98
所以个人认为应该算是归并排序。
完