14

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?

Evan Teran
  • 87,561
  • 32
  • 179
  • 238
  • 2
    In-place, *by definition*, does not require any extra memory allocations (it just requires O(1) temporary storage on the stack). Your implementation is not in-place. – Adam Rosenfield Dec 07 '10 at 04:24
  • 1
    @Adam: incorrect, it means that the results are in the same storage as the source (as opposed to just `merge` which puts the results into a buffer supplied by the caller). For example, STLPort uses temporary space in the form of: `_Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);` if you look at their implementation. – Evan Teran Dec 07 '10 at 04:27
  • 8
    After further research, it appears that there is not a single definition of "in-place" (see http://en.wikipedia.org/wiki/In-place_algorithm). The traditional definition used by algorithm theorists is one that uses O(1) extra storage, whereas the one used by the C++ standard is apparently one that uses the same storage for input and output. – Adam Rosenfield Dec 07 '10 at 04:46
  • @Adam: fair enough point. Thanks for clarifying that there is more than one way to interpret "in-place" – Evan Teran Dec 07 '10 at 05:50
  • 1
    I make the same inference as you do. Perhaps there has been a recent discovery of a O(1)-extra-memory-requiring linear-time merge, but it was unknown to the STL creators who I imagine to be a bunch of very smart people, so I regard it as unlikely. – j_random_hacker Dec 07 '10 at 07:47
  • More discussion and answers here: https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm . Indeed, the hard part in mergesort is the fast, in-place, stable merge, the rest is straightforward. – pts Jul 07 '23 at 09:05

1 Answers1

20

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?

InstallingXubuntuRightNow
  • 901
  • 5
  • 4
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Probably one of the most well documented pieces of code I saw. There a few C-isms in there (comments, casts) but it's very well presented. – Matthieu M. Dec 07 '10 at 13:49
  • +1 This answer is made of pure awesomeness and flat-out win. I'm familiar with the paper mentioned, but taking the time to implement it, even if not for this answer, then proffering it up as an live-action reference is simply stellar. Thank you. – WhozCraig Jul 07 '14 at 05:32