template <class Iterator>
void simple_quicksort(Iterator first, Iterator last)
{
  if (last - first > 1)
  {
    Iterator cut = simple_partition(first, last);
    simple_quicksort(first, cut);
    simple_quicksort(cut + 1, last);
  }  
}

template <class Iterator>
Iterator simple_partition(Iterator first, Iterator last) 
{
  std::iterator_traits<Iterator>::value_type pivot = *first;
  Iterator left = first;
  Iterator right = last;
  while (1)
  {
    do ++left; while (left != last && *left < pivot);
    do --right; while (right != first && *right > pivot);
    if (right < left)
      break;
    else
      std::iter_swap(left, right);
  }
  
  std::iter_swap(first, right);  // put pivot into correct position
  return right;
}