链接列表如何实现O(n log n)排序时间？

Question

我很好奇,首先,为什么std::list并将std::forward_list排序函数作为成员函数包含在内,与其他标准库容器不同.但对我来说更有趣的是,CPPReference和CPlusPlus都声称这种排序是在O(n log n)时间内完成的.

我甚至无法想象如何在没有随机访问元素的情况下对容器进行排序.所以我把测试组合起来,forward_list尽可能地使它变得困难.

#include <chrono>
#include <cstdint>
#include <deque>
#include <forward_list>
#include <iostream>
#include <random>

using std::endl;
using namespace std::chrono;

typedef nanoseconds::rep length_of_time;
constexpr int TEST_SIZE = 25000;


class Stopwatch
{
    public:
        void start_timing();
        void end_timing();
        length_of_time get_elapsed_time() const;
    private:
        time_point<high_resolution_clock> start;
        time_point<high_resolution_clock> end;
        length_of_time elapsed_time = 0;
};


void Stopwatch::start_timing()
{
    start = high_resolution_clock::now();
}


void Stopwatch::end_timing()
{
    end = high_resolution_clock::now();
    auto elapsed = end - start;
    auto elapsed_nanoseconds = duration_cast<nanoseconds>(elapsed);
    elapsed_time = elapsed_nanoseconds.count();
}


length_of_time Stopwatch::get_elapsed_time() const
{
    return elapsed_time;
}


std::mt19937_64 make_random_generator()
{
    using namespace std::chrono;
    auto random_generator = std::mt19937_64();
    auto current_time = high_resolution_clock::now();
    auto nanos = duration_cast<nanoseconds>(
            current_time.time_since_epoch()).count();
    random_generator.seed(nanos);
    return random_generator;
}


int main()
{
    Stopwatch timer;
    std::deque<length_of_time> times;
    auto generator = make_random_generator();
    for (int i = 1; i <= TEST_SIZE; i++) {
        std::forward_list<uint64_t> container;
        for (int j = 1; j <= i; j++) {
            container.push_front(generator());
        }
        timer.start_timing();
        container.sort();
        timer.end_timing();
        times.push_back(timer.get_elapsed_time());
        container.clear();
    }

    for (const auto& time: times) {
        std::cout << time << endl;
    }
}

该程序输出的数字给出了以下图表:

这确实看起来像O(n log n)增长(尽管每三分之一的峰值都很有趣).图书馆是如何做到这一点的？也许复制到支持排序,排序和复制的容器？

Answer 1

链接列表可以使用Mergesort在O(n log n)中排序.

有趣的是,由于链表已经具有适当的结构,因此使用Mergesort对链表进行排序只需要O(1)额外空间.

事实上,这需要专门针对列表结构调整的专用算法,这也是列表sort的成员函数,而不是单独的函数.

至于它是如何工作的 - 你需要的只是合并操作.合并操作有两个列表.您查看两个列表的头部,并删除最小的头并将其附加到结果列表中.你继续这样做,直到所有的头都被合并到大名单中 - 完成.

这是C++中的示例合并操作:

struct Node {
    Node* next;
    int val;
};

Node* merge(Node* a, Node* b) {
    Node fake_head(nullptr, 0);

    Node* cur = &fake_head;
    while (a && b) {
        if (a->val < b->val) { cur->next = a; a = a->next; }
        else                 { cur->next = b; b = b->next; }
        cur = cur->next;
    }

    cur->next = a ? a : b;
    return fake_head.next;
}