序列式容器list的排序算法笔记

序列式容器list的排序算法笔记

list 不能使用STL算法sort()，因为STL的sort函数要求random_access_iterator，而list的迭代器是bidirectional_iterator，所以必须使用自己的成员函数sort()。

SGI STL的list_sort使用的是非递归的归并排序，先将前两个元素归并，再将后两个元素归并，归并这两个小子序列成为4个元素的有序子序列；重复这一过程，得到8个元素的有序子序列，16个的，32个的……，直到全部处理完。

为何list不使用普通的merge_sort呢？这比较好理解，因为每次找到中间元素再一分为二的代价实在太大了，不适合list这种非random_access_iterator的容器。

该排序算法主要调用了swap()和merge()，而这些又依赖于内部实现的transfer()(其时间代价为O(1))。该算法时间代价亦为n*log(n)：分析代码可以发现，代码使用了64个list暂存部分有序list_node，将list总共分成n个有序list，第n个list存的node数量要么为0要么为$2^n$。

template <class T, class Alloc>
void list<T, Alloc>::sort(){
    //如果元素个数小于等于1，直接返回
    if(node->next == node || link_type(node->next)->next == node)
        return;
    // 保存下层merge返回的结果
    list<T, Alloc> carry;
    // 模拟merge sort使用的堆栈，保存部分有序的list
    // 64应该写作sizeof(size_type) * 8，即最大的递归调用层次。
    list<T, Alloc> counter[64];
    // 指示堆栈层次
    int fill = 0;
    while(!empty()){
        // 将begin处的元素从list取下，insert到carry中
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        while(i < fill && !counter[i].empty()){
            //将carry中的元素合并到counter[i]中,然后carry变为空的
            counter[i].merge(carry);
            //交换之后counter[i-1]为空
            carry.swap(counter[i++]);
        }
        // carry将结果保存到堆栈
        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]);
    }
}