title: Is it possible to do an inplace merge without temporary storage?
body: <p>I was just thinking, if I were to implement <code>std::inplace_merge</code> it would probably look something like this:</p>
  
  <pre><code>template &lt;class Bi, class Cmp&gt;
  void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
      if(first != last) {
          typedef typename iterator_traits&lt;Bi&gt;::value_type T;
          typedef typename iterator_traits&lt;Bi&gt;::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;
          }
      }
  }
  </code></pre>
  
  <p>I know that I could just use the existing implementation, but that's kind of besides the point. <strong>I was just curious if there was a better algorithm than what I am aware of.</strong></p>
  
  <p>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 <code>std::inplace_merge</code> requires an allocation by design, it seems that there is no way to control this if it were an issue.</p>
  
  <p>I think a hint at the answer comes from the standard itself regarding the complexity of <code>std::inplace_merge</code>:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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?</p>