std::merge和std::inplace_merge的用法区别
解释std::merge和std::inplace_merge的区别。merge的输入输出要求是什么？inplace_merge如何在不使用额外内存的情况下合并？各自的时间/空间复杂度如何？
回答
我是大山
std::merge(first1,last1,first2,last2,dest)将两个已排序范围合并到dest，返回dest末尾。复杂度O(n1+n2)，需要O(n1+n2)额外输出空间。要求dest不与输入范围重叠。std::inplace_merge(first,mid,last)在同一范围中原地合并两个连续的有序段[first,mid)和[mid,last)。复杂度：有足够缓冲区→O(n)；无缓冲区→O(n log n)（通过rotate等原地操作）。应用：归并排序的合并步骤、数据库join结果合并。C++17支持并行策略如std::execution::par。注意：set_union/set_intersection处理集合(去重)，而merge保留重复元素。面试高频考点：如何用merge实现set_union。