c++ - 是否可以在没有临时存储的情况下进行就地合并？

Question

我只是在想，如果我要实现 std::inplace_merge，它可能看起来像这样:

template <class Bi, class Cmp>
void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
    if(first != last) {
        typedef typename iterator_traits<Bi>::value_type T;
        typedef typename iterator_traits<Bi>::difference_type Dist;

        const Dist count = distance(first, last);
        if(count != 1) {
            // can I avoid this allocation?
            T *const temp = new T[count];       
            merge(first, middle, middle, last, temp, cmp);      
            copy(temp, temp + count, first);
            delete [] temp;
        }
    }
}

我知道我可以只使用现有的实现，但这不是重点。 我只是好奇是否有比我所知道的更好的算法。

想到这一点的原因是大多数 c++ 标准库(如果我没记错的话，所有的 STL)都允许用户指定执行分配的方式和位置，但是如果 std::inplace_merge 需要按设计分配，如果这是一个问题，似乎没有办法控制它。

我认为答案的提示来自标准本身关于 std::inplace_merge:

的复杂性

Complexity: When enough additional memory is available, (last - first) - 1 comparisons. If no additional memory is available, an algorithm with complexity N log N (where N is equal to last -first) may be used.

对我来说，这意味着已知的高效算法版本需要额外的存储空间。我读对了吗？如果是这样，有没有提到存储应该来自哪里？

Answer 1

有几种已知的就地合并算法，尽管其中一些相当复杂。它们工作的一般方式是进行异地合并，使用一些数组元素本身作为外部存储空间。我知道 Alex Stepanov 和 Paul McJones 的“编程要素”详细介绍了一种算法。

我最近阅读了一篇关于就地合并的论文，名为 "Practical In-Place Merging"详细说明了进行这种合并的一个相当简单的算法。我编码了an implementation of this algorithm以一种接近 std::inplace_merge 接口(interface)的方式，尽管有一些不同之处。也许里面有一些你可能会觉得有用的东西？