相关疑难解决方法(0)

我遇到了以下问题.

给定n个元素的数组和整数k,其中k < n.元素{ a ₀ ... a _k }和{ a _{k +1} ... a _n }已经排序.给出一个算法在O(n)时间和O(1)空间中排序.

在我看来,它不能在O(n)时间和O(1)空间中完成.问题实际上似乎是询问如何进行mergesort的合并步骤,而不是就地.如果有可能,那么不会以这种方式实现mergesort吗？我无法说服自己,但需要一些意见.