template <class Iterator>
void optimized_insertion_sort(Iterator first, Iterator last)
{
  if (first < last)
  {
    for (Iterator i = first + 1; i != last; ++i)
    {
      std::iterator_traits<Iterator>::value_type x = *i;

      // Special case: if x is the smallest item, avoid all the
      // comparisons and move it directly to the front of the container.
      if (x < *first) 
      {
	Iterator dest = i;
	Iterator src = i;
	while (src != first)
	{
	  --src;
	  *dest = *src;
	  --dest;
	}
	*first = x;
      } 
      
      // Otherwise, if x is not the smallest, we are guaranteed to
      // have a "sentinel" that ensures the inner loop below will
      // terminate, and we do not have to check to keep from going
      // past the begining of the container.
      else
      {
	Iterator src = i;
	Iterator dest = i;
	--src;
	while (x < *src) 
	{
	  *dest = *src;
	  dest = src;
	  --src;
	}
	*dest = x;
      }
    }
  }
}