Is it possible to do an inplace merge without temporary storage?
algorithm, c++
Solution
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?
Problem
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?