std::forward_list::sort 如何在 NlogN 时间内工作？

Question

我无法想象如何以合适的时间复杂度对单向链表进行重新排序（图书馆说它“大约”需要 NlogN）。是否有我可以用来查找关于它的教育 material 所用算法的名称？我查看了标准库中的代码，但除了在名为 sort 或 sort2 的少数函数之一的末尾附近发生了合并外，我想不出太多其他信息。以下是一些使用的函数：

    template <class _Pr2>
    static void _Sort(_Nodeptr _BFirst, _Pr2 _Pred) {
        auto _BMid       = _Sort2(_BFirst, _Pred);
        size_type _Bound = 2;
        do {
            if (!_BMid->_Next) {
                return;
            }

            const auto _BLast = _Sort(_BMid, _Bound, _Pred);
            _BMid             = _Inplace_merge(_BFirst, _BMid, _BLast, _Pred);
            _Bound <<= 1;
        } while (_Bound != 0);
    }

    template <class _Pr2>
    static _Nodeptr _Sort(const _Nodeptr _BFirst, size_type _Bound, _Pr2 _Pred) {
        // Sort (_BFirst, _BFirst + _Bound), unless nullptr is encountered.
        // Returns a pointer one before the end of the sorted region.
        if (_Bound <= 2) {
            return _Sort2(_BFirst, _Pred);
        }

        const auto _Half_bound = _Bound / 2;
        const auto _BMid       = _Sort(_BFirst, _Half_bound, _Pred);
        if (!_BMid->_Next) {
            return _BMid;
        }

        const auto _BLast = _Sort(_BMid, _Half_bound, _Pred);
        return _Inplace_merge(_BFirst, _BMid, _BLast, _Pred);
    }

    template <class _Pr2>
    static _Nodeptr _Inplace_merge(_Nodeptr _BFirst1, const _Nodeptr _BMid, const _Nodeptr _BLast, _Pr2 _Pred) {
        // Merge the sorted ranges (_BFirst1, _BMid] and (_BMid, _BLast)
        // Returns one before the new logical end of the range.
        auto _First2 = _BMid->_Next;
        for (;;) { // process 1 splice
            _Nodeptr _First1;
            for (;;) { // advance _BFirst1 over elements already in position
                if (_BFirst1 == _BMid) {
                    return _BLast;
                }

                _First1 = _BFirst1->_Next;
                if (_DEBUG_LT_PRED(_Pred, _First2->_Myval, _First1->_Myval)) {
                    // _First2->_Myval is out of order
                    break;
                }

                // _First1->_Myval is already in position; advance
                _BFirst1 = _First1;
            }

            // find the end of the "run" of elements less than _First1->_Myval in the 2nd range
            auto _BRun_end = _First2;
            _Nodeptr _Run_end;
            for (;;) {
                _Run_end = _BRun_end->_Next;
                if (_BRun_end == _BLast) {
                    break;
                }

                if (!_DEBUG_LT_PRED(_Pred, _Run_end->_Myval, _First1->_Myval)) {
                    // _Run_end is the first element in (_BMid->_Myval, _BLast->_Myval) that shouldn't precede
                    // _First1->_Myval.
                    // After the splice _First1->_Myval will be in position and must not be compared again.
                    break;
                }

                _BRun_end = _Run_end;
            }

            _BMid->_Next     = _Run_end; // snip out the run from its old position
            _BFirst1->_Next  = _First2; // insert into new position
            _BRun_end->_Next = _First1;
            if (_BRun_end == _BLast) {
                return _BMid;
            }

            _BFirst1 = _First1;
            _First2  = _Run_end;
        }
    }

Answer 1

合并排序的“自下而上”变体可以在 O(n log n) 时间和 O(1) space 中对链表进行排序。 See the Wikipedia article。如果 O(1) space 不是必需的，那么您可以在列表中构造一个指针数组，使用任何 O(n log n) 排序算法对其进行排序，然后从排序后的副本重建列表。

std::forward_list::sort 如何在 NlogN 时间内工作？

How Does std::forward_list::sort Work in NlogN Time?

c++

sorting

stl