c++ - 如果范围没有排序，inplace_merge 会做什么？

Question

inplace_merge的文档说“必须对范围进行排序”。但是，它没有说明如果范围没有排序会发生什么。我尝试将它与未排序的范围一起使用，结果是一个未排序的数组，但这可能与编译器有关。我可以从缺少有关此案例的文档中得出什么结论-这是否意味着，如果范围未排序，则结果是未定义的行为？（例如：是否允许符合标准的编译器在范围未排序的情况下创建分段错误？）

标签： c++stl

Answer 1

inplace_merge需要对输入进行排序，这在[alg.merge]中指定：

要求：[first, middle)和[middle, last)应是相对于和排序的有效范围。compproj

所以严格来说，提供未分类的输入inplace_merge是未定义的行为，故事的结尾。

但该标准还要求它是稳定的和O(N) 复杂度。

这给我们带来了唯一可能的实现，使用双指针算法：同时遍历两个范围，通过在每一步从两者中选择最小的元素将它们“压缩”在一起。

因此，在实践中，它很可能会执行完成，结果未排序。