VS 2010 std::list.sort函数实现的非递归merge sort
td::list.sort()采用的是mergesort算法。
merge sort的递归实现非常简单，一般为
MergeSort(1,n){
MergeSort(1,n/2);
MergeSort(n/2,n);
Merge(1,n/2,n);
}
下图为用一个长度为16的序列调用MergeSort形成的归并树（节点中的m..n是序列的下标，虚三角表示省略的子树）
std::list.sort()虽然采用了merge sort算法，但实现上采用了非递归的方式。代码原文见最后，以下是对于代码的详细分析：
_Binlist为list的数组，数组长度为26。
while (!empty())保持了以下循环不变量：
1. _Maxbin<=25
2. 如果n属于[0,_Maxbin)，且n!=24，则_Binlist[n]或者为空，或者保存了已经排好序的2^^n个元素
3. 如果n属于[0,_Maxbin)，且n==24，则_Binlist[n]或者为空，或者保存了已经排好序的>=2^^n个元素
4. 如果n>=_Maxbin，_Binlist[n]为空
因此，执行完while后，后续的操作把[0,_Maxbin)范围的list全部归并起来，形成了最终的排序序列。
这里有趣的是元素的归并过程。
从逻辑上，可以认为_Binlist[n]为空，则_Binlist[n]取值为1，否则取值为0。因此_Binlist形成了一个二进制"0"和"1"的序列，即_Binlist逻辑上形成了一个整数。每次while循环处理一个新的元素，会导致_Binlist的list依次从低向高归并，归并的结果相当于向_Binlist整数加1；同时，_Binlist[n]取值为1或0的含义保持不变。
通过跟踪可知，std::list.sort()的归并树与递归调用完全相同。
_Binlist数组形成的逻辑整数
算法原文：
void sort()
{ // order sequence, using operator<
if (2 <= this->_Mysize)
{ // worth sorting, do it
const size_t _MAXBINS = 25;
_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1];
size_t _Maxbin = 0;
while (!empty())
{
// assert _Templist.size() == 0
// sort another element, using bins
// 每次循环处理一个元素
_Templist._Splice_same(_Templist.begin(), *this, begin(),
++begin(), 1);
size_t _Bin;
for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty();
++_Bin)
{ // merge into ever larger bins
_Binlist[_Bin].merge(_Templist);
_Binlist[_Bin].swap(_Templist);
}
if (_Bin == _MAXBINS)
_Binlist[_Bin - 1].merge(_Templist);
else
{ // spill to new bin, while they last
// assert _Binlist[_Bin].empty()
_Binlist[_Bin].swap(_Templist);
if (_Bin == _Maxbin)
++_Maxbin;
}
}
// 从前到后合并_Bin数组，最后插入到self中
for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
_Binlist[_Bin].merge(_Binlist[_Bin - 1]); // merge up
splice(begin(), _Binlist[_Maxbin - 1]); // result in last bin
}
}
