我只是在想，如果要实施，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：

复杂度：当有足够的额外内存可用时，（最后-首先）-1个比较。如果没有额外的可用内存，则可以使用复杂度为N log N（其中N等于倒数第一）的算法。

对我而言，这意味着该算法的已知有效版本需要额外的存储。我读对了吗？如果是这样，是否有提及存储的来源？