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

Question

documentation to inplace_merge说“范围必须排序”。但是，它没有说明如果范围未排序会发生什么。我尝试将它与未排序的范围一起使用，结果是一个未排序的数组，但这可能取决于编译器。由于缺乏有关此案例的文档，我可以得出什么结论 - 这是否意味着，如果范围未排序，结果是 undefined behavior ？ (例如:如果范围未排序，是否允许符合标准的编译器创建段错误？)

Answer 1

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

Requires: [first, middle) and [middle, last) shall be valid ranges sorted with respect to comp and proj.

严格来说，向 inplace_merge 提供未排序的输入是 undefined behavior ，故事结束。

但标准还要求它稳定并且O(N) complexity .

这给我们带来了唯一可能的实现，使用 two-pointer algorithm :同时遍历两个范围，通过在每一步中选择最小的元素将它们“压缩”在一起。

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