#line 5846 "smat.w"
#ifndef _LOMUTO_H_
#define _LOMUTO_H_


#line 5861 "smat.w"
template <typename Iter, typename ValueType>
Iter
lomuto_partition_pivot(Iter first, Iter last, ValueType pivot)
{
  Iter lessthan = first - 1;
  for ( ; first != last; ++first)
    {
      if (*first < pivot)
        iter_swap(++lessthan, first);
    }
  return lessthan + 1;
}
#line 5849 "smat.w"


#line 5892 "smat.w"
template <typename Iter, typename Size>
void
lomuto_introsort_loop(Iter first, Iter last, Size depth_limit)
{
  typedef typename std::iterator_traits<Iter>::value_type ValueType;

  while (last - first > _M_threshold)
    {
      if (depth_limit == 0)
        return partial_sort(first, last, last);
      --depth_limit;
      Iter cut =
        lomuto_partition_pivot(first, last,
                               ValueType(__median(*first,
                                                  *(first + (last - first)/2),
                                                  *(last - 1))));
      lomuto_introsort_loop(cut, last, depth_limit);
      last = cut;
    }
}
#line 5850 "smat.w"


#line 5880 "smat.w"
template <typename Iter>
inline void
lomuto_introsort(Iter first, Iter last)
{
  if (first != last)
    {
      lomuto_introsort_loop(first, last, __lg(last - first) * 2);
      __final_insertion_sort(first, last);
    }
}
#line 5851 "smat.w"


#endif // _LOMUTO_H_