A sketch of inplace_merge

inplace_merge.cpp

#include <cassert>
#include <iterator>
#include <memory>
#include <utility>

template <typename ForwardIt>
void my_inplace_merge(ForwardIt first, ForwardIt middle, ForwardIt last)
{
  if (first == middle || middle == last) return;

  using T = typename std::iterator_traits<ForwardIt>::value_type;

  // call the range [first, middle) x, and the range [middle, last) y
  // make a buffer big enough to hold the smaller range
  auto d1 = std::distance(first, middle);
  auto d2 = std::distance(middle, last);

  // we're going to write to the range in place
  ForwardIt out = first;

  // we're going to read from each range
  ForwardIt readx = first;
  ForwardIt ready = middle;

  // and we're going to read and write from tmp. tmp is a buffer than can hold
  // values, but we don't know that T is default constructible, so make a char
  // buffer big enough
  auto n = std::min(d1, d2);
  auto tmp = std::make_unique<char[]>(n * sizeof(T));

  // we're going to use tmp as a ring buffer
  T* begint = reinterpret_cast<T*>(tmp.get());
  T* endt = begint + n;
  T* readt = begint;
  T* writet = begint;
  bool tmp_full = false;

  // loop until we reach the end of either x or y
  while (readx != middle && ready != last)
  {
    if (readt != writet)
    {
      // the next lowest x value is in tmp
      if (*ready < *readt)
      {
        // x -> tmp, y -> out
        *writet++ = std::move(*readx);
        if (writet == endt) writet = begint;

        *out = std::move(*ready);
        ++ready;

        tmp_full = writet == readt;
      }
      else
      {
        // x -> tmp, tmp -> out
        *writet++ = std::move(*readx);
        if (writet == endt) writet = begint;

        *out = std::move(*readt);
        ++readt;
        if (readt == endt) readt = begint;
      }
    }
    else
    {
      // tmp is currently empty, we're comparing the x with y directly
      if (*ready < *readx)
      {
        // x -> tmp, y -> out
        *writet++ = std::move(*readx);
        if (writet == endt) writet = begint;

        *out = std::move(*ready);
        ++ready;

        tmp_full = writet == readt;
      }
    }
    ++readx;
    ++out;

    // if the temporary buffer is full, we must have exhausted either x or y
    assert(!tmp_full || readx == middle || ready == last);
  }

  if (out == middle)
  {
    // any remaining values of x are now in tmp, so do a "normal" merge from tmp
    // and y to out
    while (readt != writet || tmp_full)
    {
      if (ready != last && *ready < *readt)
      {
        *out++ = std::move(*ready);
        ++ready;
      }
      else
      {
        *out++ = std::move(*readt);
        ++readt;
        if (readt == endt) readt = begint;
        tmp_full = false;
      }
    }
  }
  else if (ready == last)
  {
    // all the values of y are accounted for, and we know that all the values of
    // x in tmp are less than the remaining ones, so swap tmp with x repeatedly
    // until we reach the middle, then output the remaining tmp
    using std::swap;
    T* p = readt;
    while (out != middle)
    {
      swap(*p, *out);
      ++p, ++out;
      if (p == endt) p = begint;
      if (p == writet) p = readt;
    }
    while (out != last)
    {
      *out = std::move(*p);
      ++p, ++out;
      if (p == endt) p = begint;
      if (p == writet) p = readt;
    }
  }
}

#include <algorithm>

template <typename ForwardIt>
void naive_inplace_merge(ForwardIt first, ForwardIt middle, ForwardIt last)
{
  while (first != middle && middle != last)
  {
    if (*middle < *first)
    {
      std::iter_swap(middle, first);
      auto i = middle;
      std::rotate(++first, i, ++middle);
    }
    else
    {
      ++first;
    }
  }
}

template <typename BidirIt>
void naive_inplace_merge2(BidirIt first, BidirIt middle, BidirIt last)
{
  using T = typename std::iterator_traits<BidirIt>::value_type;

  auto d1 = std::distance(first, middle);
  auto d2 = std::distance(middle, last);

  auto n = std::min(d1, d2);
  auto tmp = std::make_unique<char[]>(n * sizeof(T));
  T* begint = reinterpret_cast<T*>(tmp.get());
  T* endt = begint + n;

  if (d1 <= d2)
  {
    std::move(first, middle, begint);
    std::merge(begint, endt, middle, last, first);
  }
  else
  {
    std::move(middle, last, begint);
    auto i = std::move_backward(first, middle, last);
    std::merge(i, last, begint, endt, first);
  }
}

#include <forward_list>
#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
  // some tests

  // split at 5
  // vector<int> v{0,2,4,6,8,1,3,5,7,9};
  // vector<int> v{0,1,2,3,4,5,6,7,8,9};
  // vector<int> v{5,6,7,8,9,0,1,2,3,4};
  // forward_list<int> v{5,6,7,8,9,0,1,2,3,4};
  // typename decltype(v)::difference_type split = 5;

  // split at 3
  // vector<int> v{0,1,2,3,4,5,6,7,8,9};
  // vector<int> v{7,8,9,0,1,2,3,4,5,6};
  // forward_list<int> v{7,8,9,0,1,2,3,4,5,6};
  // typename decltype(v)::difference_type split = 3;

  // split at 7
  // vector<int> v{0,1,2,3,4,5,6,7,8,9};
  // vector<int> v{3,4,5,6,7,8,9,0,1,2};
  forward_list<int> v{3,4,5,6,7,8,9,0,1,2};
  typename decltype(v)::difference_type split = 7;

  auto b = v.begin();
  auto m = b;
  advance(m, split);
  auto e = v.end();

  my_inplace_merge(b, m, e);

  for (auto i : v)
    cout << i << ", ";
  cout << endl;
}