Merges and mergesort

As long as we're on the topic of sorting algorithms, let's write sort a different way!

std::inplace_merge(a,mid,b) takes a single range [a,b) which has already been sorted with the equivalent of std::sort(a,mid) and std::sort(mid,b), and merges the two subranges together into a single sorted range. We can use this building block to implement the classic mergesort algorithm:

    template<class RandomIt>
    void sort(RandomIt a, RandomIt b)
    {
      auto n = std::distance(a, b);
      if (n >= 2) {
        auto mid = a + n/2;
        std::sort(a, mid);
        std::sort(mid, b);
        std::inplace_merge(a, mid, b);
      }
    }

However, beware! The name inplace_merge seems to imply that the merging is happening "in-place" without the need for any additional buffer space; but this is not what happens in fact. In actuality, the inplace_merge function allocates a buffer for its own use, typically by calling operator new. If you are programming in an environment...