排序相关的二三事

写在前面

国庆在家里实在是无聊透顶，在写算法题的时候发现一个事情，c++的std::sort是不支持链式数据结构的，所以就想着能不能做一个给单向链表排序的排序算法。所有相关代码被放在 GITEE:dxyinme/Vsort

具体要怎么做

我们先设计了一个单链表结构VListNode如下：

template<typename T>
struct VListNode {
  T val;
  VListNode *nxt;
};

如果我们要合并两个有序的单链表，那么我们就只需要每次选择一个链表里面最大的元素就可以。这个很简单，详见 Vsort::MergeList，可以合并两个有序单向链表的话，我们就可以做一个归并排序，每次O(n)选取整个链表的中点，将整个链表从中点切成两个链表，切完之后，递归继续，直到只剩下一个元素为止。

我们对于

优化

单只有链表排序肯定不够，而且性能也普通的std::sort对vector排序比差了不少，是否可以进行一个多线程的优化。
整个多线程排序分成三个部分：

1. 我们将整个待排序容器切成若干部分 (同步)
2. 每个部分排序 (异步)
3. 合并每个已经排序的部分 (异步)