template <class Iterator>
void nonrecursive_merge_sort(Iterator first, Iterator last)
{
  typedef std::iterator_traits<Iterator>::value_type T;
  int len = last - first;
  T * buf = new T[len];
  T * buf_last = buf + len;
  int step_size = 1;

  // Optimization; make step_size > 1.
  Iterator p = first;
  while (last - p >= step_size) 
  {
    insertion_sort(p, p + step_size);
    p += step_size;
  }
  insertion_sort(p, last);

  while (step_size < len) 
  {
    nonrecursive_merge_sort_loop(first, last, buf, step_size);
    step_size *= 2;
    nonrecursive_merge_sort_loop(buf, buf_last, first, step_size);
    step_size *= 2;
  }
}

template <class Iterator1, class Iterator2>
void nonrecursive_merge_sort_loop(Iterator1 first, Iterator1 last, 
                                  Iterator2 result, int step_size)
{
  int twice_step_size = 2 * step_size;

  while (last - first >= twice_step_size) 
  {
    result = merge(first, first + step_size,
                   first + step_size, first + twice_step_size,
                   result);
    first += twice_step_size;
  }

  step_size = std::min(last - first, step_size);
  merge(first, first + step_size, first + step_size, last, result);
}