#line 5782 "smat.w"
#ifndef _EARLY_H_
#define _EARLY_H_


#line 5818 "smat.w"
template <typename Iter, typename Size>
void
early_introsort_loop(Iter first, Iter last, Size depth_limit,
                     const Iter& real_first)
{
  typedef typename std::iterator_traits<Iter>::value_type ValueType;

  while (last - first > _M_threshold) // 16
    {
      if (depth_limit == 0)
        return partial_sort(first, last, last);
      --depth_limit;
      Iter cut =
        __unguarded_partition(first, last,
                              ValueType(__median(*first,
                                                 *(first + (last - first)/2),
                                                 *(last - 1))));
      early_introsort_loop(cut, last, depth_limit, real_first);
      last = cut;
    }
  if (first == real_first)
    __insertion_sort(first, last);
  else
    __unguarded_insertion_sort(first, last);
}
#line 5785 "smat.w"


#line 5798 "smat.w"
template<typename Iter>
inline void
early_introsort(Iter first, Iter last)
{
  if (first != last)
    early_introsort_loop(first, last, __lg(last - first) * 2, first);
}
#line 5786 "smat.w"


#endif // _EARLY_H_