c++ - 对部分已排序的 std::vector 进行排序（由已排序向量的串联形成）

Question

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

我需要对这个向量进行排序。我想知道哪种排序算法最适合。我更喜欢像合并或快速这样的就地排序算法，因为我不想占用更多内存（向量已经很大了）。

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

所以理想情况下，我更喜欢在大向量上使用一些现成的排序算法的方法（因为我觉得这会更简单）。

Answer 1

看看std::inplace_merge。您可以使用合并排序思想并合并每一对，然后合并下一对，然后下一个……以此类推，直到只剩下一个。

Answer 2

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

要查找连接点，您可以查找从一开始就违反排序标准的第一个元素。然后从那个位置到下一个位置，依此类推..

Answer 3

Timsort看起来正是您所需要的——它是一种自适应排序，可以在数据中查找预排序的运行，并在运行时将它们合并。它具有最坏情况下的 O(nlog n) 性能，我希望它会比运行（预排序的子数组）很长的情况好得多。