Is it possible to do an inplace merge without temporary storage?

Question

I was just thinking, if I were to implement std::inplace_merge it would probably look something like this:

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;
        }
    }
}

I know that I could just use the existing implementation, but that's kind of besides the point. I was just curious if there was a better algorithm than what I am aware of.

The reason this came to mind is that most of the c++ standard library (all of the STL if I recall correctly) lets the user specify how and where to perform allocations, but if std::inplace_merge requires an allocation by design, it seems that there is no way to control this if it were an issue.

I think a hint at the answer comes from the standard itself regarding the complexity of 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.

To me this implies that the known efficient versions of the algorithm require extra storage. Am I reading that right? If so, is there any mention of where the storage is supposed to come from?

Answer 1

There are several known algorithms for merging in-place, though some of them are fairly complex. The general way in which they work is doing an out-of-place merge, using some of the array elements themselves as the external storage space. I know that Alex Stepanov and Paul McJones' "Elements of Programming" details one algorithm.

I recently read a paper on in-place merging called "Practical In-Place Merging" that details a fairly simple algorithm for doing this sort of merge. I coded up an implementation of this algorithm in a way that is close to the interface of std::inplace_merge, though there are a few differences. Perhaps there's something in there that you might find useful?