对一个std::vector进行排序，这个vector的部分已经排好序（由已排序向量的连接形成）。

Question

我有一个std :: vector作为要公开的API的输入之一。 我知道此API的用户可以发送一个巨大的向量，但该向量是由排序向量的连接形成的。这意味着我得到的向量是由多个排序向量组成的。

我需要对此向量进行排序。 我想知道哪种排序算法最适合。 我希望使用类似于合并或快速排序的就地排序算法，因为我不想占用更多内存（向量已经很大）。

另外，是否更好将API接口更改为接受N个排序向量，然后自己执行N路合并。除非节省真的很大，否则我不想这样做。同时，在进行N路合并时，如果可能的话，我希望在原地执行。

因此，理想情况下，我希望采用一些现成的排序算法来处理大向量（因为我觉得这样会更简单）。

- AMM

Answer 1

看看std::inplace_merge。你可以使用归并排序的思想，将每一对合并，然后合并下一对，再下一对...依此类推，直到只剩下一个。

- Artem Sobolev

Answer 2

你可以搜索向量以找到较小向量的连接点。然后通过使用这些迭代器，您可以逐个进行合并。

要找到连接点，您可以从开头开始寻找第一个违反排序条件的元素。然后从该位置到下一个位置依此类推。

- user995502

Answer 3

TimSort 看起来正是你需要的东西——它是一种自适应排序算法，它在数据中寻找预排序的序列，并在处理过程中将它们合并。它具有最坏情况下 O(nlog n) 的性能，如果这些预排序的序列很长的话，我相信它的表现会更好。

- j_random_hacker