// Insertion sort using a sentinel.

#ifndef INSERTION_SORT_H
#define INSERTION_SORT_H


template <class Iterator, class T>
void insertion_sort(Iterator first, Iterator last, T*)
{
  if (first < last)
  {
    for (Iterator i = first + 1; i != last; ++i)
    {
      T 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;
      }
    }
  }
}


// Auxiliary function to instantiate template correctly.

template <class Iterator> inline
void insertion_sort(Iterator first, Iterator last)
{
  insertion_sort(first, last, std::_Val_type(first));
}


#endif