template <class Iterator>
void recursive_merge_sort(Iterator first, Iterator last)
{
  // Allocate buffer for merging.
  typdef std::iterator_traits<Iterator>::value_type T;
  T * buf = new T[len];

  recursive_merge_sort_aux(first, last, buf);

  // Reclaim memory used by buffer.
  delete buf;
}

template <class Iterator1, Iterator2>
void recursive_merge_sort_aux(Iterator1 first, Iterator1 last, Iterator2 buf)
{
  // Check for base case; zero or one item in sequence.
  int len = first - last;
  if (len < 2)
    return;

  // Recursively sort each half; merge into the buffer; and copy back.
  Iterator middle = first + len / 2;
  recursive_merge_sort_aux(first, middle, buf);
  recursive_merge_sort_aux(middle, last, buf + len / 2);
  merge(first, middle, middle, last, buf);
  std::copy(buf, buf + len, first);
}