SGI STL笔记（list中的sort算法）

STL的list容器提供了专有的sort算法，是一个以非递归形式的merge sort，虽然研究多时，无奈本人算法功底不济，本文权当抛砖引玉，望各路高手指点。

代码：

template <class _Tp, class _Alloc>
template <class _StrictWeakOrdering>
void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
{
    // Do nothing if the list has length 0 or 1.
    if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
        // 保存下层merge返回的结果
        list<_Tp, _Alloc> __carry;
        // 模拟merge sort使用的堆栈，保存部分有序的list
        // 64应该写作sizeof(size_type) * 8，即最大的递归调用层次。
        list<_Tp, _Alloc> __counter[64];
        // 指示堆栈层次
        int __fill = 0;
        while (!empty()) {
            // 将begin处的元素从list取下，insert到carry中
            __carry.splice(__carry.begin(), *this, begin());
            int __i = 0;
            // 模拟递归时对下层的返回结果进行merge，并将结果交给carry
            while(__i < __fill && !__counter[__i].empty()) {
                __counter[__i].merge(__carry, __comp);
                __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], __comp);
        // 保存最终结果
        swap(__counter[__fill-1]);
    }
}

再免费赠送一个正常merge sort的C实现：）

void merge(int *vector, size_t size)
{
    // return if there's 0 or 1 element.
    if (size <= 1) {
        return ;
    }

    int half = size / 2;

    merge(vector, half);
    merge(vector + half, size - half);

    merge_aux(vector, size);

    return ;
}

static void merge_aux(int *vector, size_t size)
{
    int i, j, k;

    int half = size / 2;

    int clone[half];

    for (i = 0; i < half; ++i) {
        clone[i] = vector[i];
    }

    for (i = 0, j = half, k = 0; (i < half) && (j < size); ++k) {
        if (clone[i] < vector[j]) {
            vector[k] = clone[i++];
        }
        else {
            vector[k] = vector[j++];
        }
    }

    while (i < half) {
        vector[k++] = clone[i++];
    }

    return ;
}

以下以对数据（5, 4, 3, 2, 1）排序为例，比较二者的主要差别。

1）递归形式：（圆圈内为本层排序好的数据）

图1

因为递归形式的merge sort在每一层都对数据进行分解，所以递归树是一棵完全二叉树。

2）非递归形式：

图2

因为非递归形式的算法是自底向上来merge数据，原始数据都处在同一层上，所以部分数据缺少中间的层次，最后仍然需要对这些结果再做一次合并（图2虚线引出的那些单元，就是由list::sort中最后那个for循环所处理）。

另外，由list本身来提供sort算法并不符合STL的设计原则，但若要将这样一个严重依赖底层实现的算法抽象出来，又需要做哪些改动呢？欢迎大家讨论。