请注意，此答案已更新为解决以下注释中以及问题之后提到的所有问题，方法是从列表数组到迭代器数组进行相同的更改，同时保留了更快的自下而上合并排序算法，并消除了由于使用自上而下的合并排序算法进行递归，因此堆栈溢出的可能性很小。

我最初不考虑迭代器的原因是由于VS2015自上而下的更改，使我认为尝试更改现有的自下而上算法以使用迭代器存在一些问题。只有当我尝试自己分析对迭代器的转换时，我才意识到存在解决方案。

在@sbi的评论中，他询问自上而下的方法的作者Stephan T.
Lavavej为何进行了更改。Stephan的回应是“避免内存分配和默认构造分配器”。VS2015引入了非默认可构造且有状态的分配器，这在使用先前版本的列表数组时会出现问题，因为列表的每个实例都会分配一个虚拟节点，并且需要进行更改以处理默认分配器。

Lavavej的解决方案是切换到使用迭代器来跟踪原始列表内而不是内部列表内的运行边界。合并逻辑已更改为使用3个迭代器参数，第一个参数是迭代器，以左行开始，第二个参数是迭代器，以左行结束==迭代器，以右行开始，第三个参数是迭代器，以右行结束。合并过程在合并操作期间使用std
:: list ::
splice在原始列表内移动节点。这具有异常安全的附加好处。如果调用者的compare函数引发异常，则将对列表进行重新排序，但不会发生数据丢失（假定接合不会失败）。使用先前的方案，如果发生异常，某些（或大多数）数据将在列表的内部数组中，并且数据将从原始列表中丢失。

但是，不需要切换到自上而下的合并排序。最初，我认为VS2015切换到自上而下的原因有些未知，我专注于以与std :: list ::
splice相同的方式使用内部接口。后来，我决定研究自下而上的开关，以使用迭代器数组。我意识到内部数组中存储的运行顺序是最新的（array [0]
=最右边）至最旧的（array [last] =最左边），并且它可以使用与VS2015自上而下的方法相同的基于迭代器的合并逻辑。

对于自下而上的合并排序，array [i]是具有2 ^ i个节点的已排序子列表开头的迭代器，或者为空（使用std :: list ::
end表示为空）。每个排序后的子列表的末尾将是数组中下一个先前的非空条目中排序后的子列表的开始，或者如果是数组的开始，则是本地迭代器中的排序子列表的开始（它指向最新的末尾）跑）。与自顶向下方法类似，迭代器数组仅用于跟踪原始链表中已排序的运行边界，而合并过程使用std
:: list :: splice在原始链表中移动节点。

如果链表很大并且节点分散，那么将有很多缓存未命中。自下而上的速度比自下而上的速度快30％（相当于说自上而下的速度比自下而上的速度慢42％）。再说一次，如果有足够的内存，通常将列表移动到数组或向量，对数组或向量排序，然后从排序后的数组或向量创建新列表通常会更快。

示例C ++代码：

#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    std::list<T>::iterator ai[ASZ];     // array of iterators
    std::list<T>::iterator mi;          // middle iterator (end lft, bgn rgt)
    std::list<T>::iterator ei;          // end    iterator
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array
    for (ei = ll.begin(); ei != ll.end();) {
        mi = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            mi = Merge(ll, ai[i], mi, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = mi;
    }
    // merge array into single list
    ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    mi = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        mi = Merge(ll, ai[i++], mi, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator mi,
                             typename std::list<T>::iterator ei)
{
    std::list<T>::iterator ni;
    (*mi < *li) ? ni = mi : ni = li;
    while(1){
        if(*mi < *li){
            ll.splice(li, ll, mi++);
            if(mi == ei)
                return ni;
        } else {
            if(++li == mi)
                return ni;
        }
    }
}

VS2019的std :: list :: sort（）的示例替换代码（合并逻辑已制成单独的内部函数，因为现在已在两个地方使用它）。

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of   iterators to runs
        iterator _Mi;                   // middle     iterator
        iterator _Li;                   // last (end) iterator
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array runs into single run
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }

这个答案的其余部分是历史性的。

我能够根据来自@IgorTandetnik的演示重现该问题（旧排序无法编译，新版本可以工作）：

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor

    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}

    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

我在2016年7月注意到了这一变化，并在2016年8月1日通过电子邮件将其告知了PJPlauger。他的摘录片段：

有趣的是，我们的更改日志未反映此更改。这可能意味着它是由我们的一个较大客户“建议”的，并由我在代码审查中获得。我现在所知道的是，更改是在2015年秋天左右进行的。当我查看代码时，让我印象深刻的第一件事是：

    iterator _Mid = _STD next(_First, _Size / 2);

当然，对于大量列表而言，这可能需要 很 长时间。

该代码看起来比我在1995年初编写的代码更优雅（！），但是肯定具有更差的时间复杂度。该版本以Stepanov，Lee和Musser在原始STL中的方法为蓝本。在选择算法时很少发现它们是错误的。

我现在要恢复到原始代码的最新已知良好版本。

我不知道PJ Plauger还原到原始代码是否处理了新的分配器问题，或者Microsoft是否或如何与Dinkumware进行交互。

为了比较自上而下和自下而上的方法，我创建了一个包含400万个元素的链表，每个元素由一个64位无符号整数组成，假设我最终得到的是几乎按顺序排序的节点的双链表（即使它们（将被动态分配），用随机数填充它们，然后对其进行排序。节点不会移动，只会更改链接，但是现在遍历列表将以随机顺序访问节点。然后，我用另一组随机数填充这些随机排序的节点，然后再次对其进行排序。我将2015年自上而下的方法与先前的自下而上的方法进行了比较，以适应2015年所做的其他更改（sort（）现在使用谓词compare函数而不是两个单独的函数调用sort（））。这些就是结果。
更新 -我添加了一个基于节点指针的版本，还记下了从列表简单创建向量，对向量进行排序，复制回来的时间。

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

对于顺序节点，先前版本仅快一点，但是对于随机节点，先前版本快30％，节点指针版本快35％，并从列表中创建向量，对向量进行排序，然后复制回去快了69％。

以下是std :: list :: sort（）的第一个替换代码，我以前使用小数组（_BinList
[]）方法与VS2015的自上而下方法进行了比较，我希望这种比较是公平的，因此我修改了<列表>的副本。

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don't go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller's list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

我做了一些小改动。原始代码在名为_Maxbin的变量中跟踪实际的最大bin，但是最终合并中的开销很小，以至于我删除了与_Maxbin相关的代码。在数组构建期间，原始代码的内部循环合并为_Binlist
[]元素，然后交换为_Templist，这似乎毫无意义。我将内部循环更改为仅合并到_Templist中，仅在找到空的_Binlist []元素后才进行交换。

下面是基于std :: list ::sort（）的基于节点指针的替换，我将其用于另一个比较。这消除了与分配有关的问题。如果可能发生比较异常，则必须将阵列和临时列表（pNode）中的所有节点附加回原始列表，否则可能会将比较异常视为小于比较。

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }