typedef cmt_string T;

typedef T* RandomAccessIterator;
typedef T* BidirectionalIterator1;
typedef T* BidirectionalIterator2;
typedef T* ForwardIterator1;
typedef T* ForwardIterator2;

//template <class ForwardIterator1, class ForwardIterator2, class T>
void iter_swap (ForwardIterator1 a, ForwardIterator2 b, T*)
{
  T tmp = *a;
  *a = *b;
  *b = tmp;
}

//template <class RandomAccessIterator, class T>
RandomAccessIterator unguarded_partition (RandomAccessIterator first,
                                          RandomAccessIterator last,
                                          T pivot)
{
  while (true)
    {
      while (*first < pivot) ++first;
      --last;
      while (pivot < *last) --last;

      if (!(first < last)) return first;

      iter_swap (first, last, first);

      ++first;
    }
}

//template <class T>
const T& median (const T& a, const T& b, const T& c)
{
  if (a < b)
    if (b < c)
      return b;
    else if (a < c)
      return c;
    else
      return a;
  else if (a < c)
    return a;
  else if (b < c)
    return c;
  else
    return b;
}

const int threshold = 16;

//template <class RandomAccessIterator, class T>
void quick_sort_loop (RandomAccessIterator first,
                      RandomAccessIterator last, T* t)
{
  while ((last - first) > threshold)
    {
      RandomAccessIterator cut = unguarded_partition
          (first,
           last,
           T (median(*first,
                     *(first + (last - first)/2),
                     *(last - 1))));

      T pivot = median(*first,
                       *(first + (last - first)/2),
                       *(last - 1));

      if (cut - first >= last - cut)
        {
          quick_sort_loop (cut, last, t);
          last = cut;
        }
      else
        {
          quick_sort_loop (first, cut, t);
          first = cut;
        }
    }
}

//template <class RandomAccessIterator, class T>
void unguarded_linear_insert (RandomAccessIterator last, T value)
{
  RandomAccessIterator next = last;
  --next;
  while (value < *next)
    {
      *last = *next;
      last = next--;
    }
  *last = value;
}

//template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward (BidirectionalIterator1 first,
                                      BidirectionalIterator1 last,
                                      BidirectionalIterator2 result)
{
    while (first != last) *--result = *--last;
    return result;
}

//template <class RandomAccessIterator, class T>
void linear_insert (RandomAccessIterator first,
                    RandomAccessIterator last, T*)
{
  T value = *last;
  if (value < *first)
    {
      copy_backward(first, last, last + 1);
      *first = value;
    }
  else
    unguarded_linear_insert (last, value);
}

//template <class RandomAccessIterator>
void insertion_sort (RandomAccessIterator first, RandomAccessIterator last)
{
  if (!(first == last))
    for (RandomAccessIterator i = first + 1; i != last; ++i)
      linear_insert(first, i, first);
}

//template <class RandomAccessIterator, class T>
void unguarded_insertion_sort (RandomAccessIterator first,
                               RandomAccessIterator last, T*)
{
  for (RandomAccessIterator i = first; i != last; ++i)
    unguarded_linear_insert (i, T(*i));
}

//template <class RandomAccessIterator>
void final_insertion_sort (RandomAccessIterator first,
                           RandomAccessIterator last)
{
  if (last - first > threshold)
    {
      insertion_sort (first, first + threshold);
      unguarded_insertion_sort (first + threshold, last, first);
    }
  else
    insertion_sort (first, last);
}

//template <class RandomAccessIterator>
void sort (RandomAccessIterator first,
           RandomAccessIterator last)
{
  if (!(first == last))
    {
      quick_sort_loop (first, last, first);
      final_insertion_sort (first, last);
    }
}