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

I can't imagine how to reorder a singly linked list with decent time complexity (The library says it takes "approximately" NlogN). Is there a name for the algorithm used that I could use to find educational material about it? I looked at the code in the standard library, but I couldn't figure much out other than a merge takes place near the end of one of the few functions named sort or sort2. Below are some of the functions used:

    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;
        }
    }

CodePudding user response：

"Bottom up" variants of merge sort can sort a linked list in O(n log n) time and O(1) space. See the Wikipedia article. If O(1) space isn't a requirement then you can construct an array of pointers into the list, sort that using any O(n log n) sorting algorithm, and then rebuild the list from your sorted copy.