c++ - 链表如何实现 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;
}