@*Insertion Sort.

@ Introduction and Description.

{\bf[Input]:}  A list of objects.

{\bf[Output]:}  The sorted list of all objects passed as input.

@ Algorithm.

The algorithm is exactly the same as the algorithm people intuitively use to 
sort a deck of cards. Each time take the smallest or largest object and 
put it at the end of the smallest already sorted sub-list of the original list.

@<Insertion Sort@>=
template <class RandomAccessIter>
void insertion_sort(RandomAccessIter first,
		RandomAccessIter last)
{
// starts from the seond element in list upto last element
typename std::iterator_traits<RandomAccessIter>::value_type key;
for (RandomAccessIter iter = first + 1; iter != last + 1; ++iter) {
	key = *iter;

	RandomAccessIter i = iter - 1;
	while ((key < *i) && (i != first)) {
		*(i + 1) = *i;
		--i;
	} // while key and i

	*(i + 1) = key;
} // for iter


} // end of |insertion_sort()|

template <class RandomAccessIter, class Compare>
void insertion_sort(RandomAccessIter first, 
		RandomAccessIter last, 
		Compare cmp)
{
// starts from the seond element in list upto last element
typename std::iterator_traits<RandomAccessIter>::value_type key;
for (RandomAccessIter iter = first + 1; iter != last + 1; ++iter) {
	key = *iter;

	RandomAccessIter i = iter - 1;
	while (pred(key, *i) && (i != first)) {
		*(i + 1) = *i;
		--i;
	} // while key and i

	*(i + 1) = key;
} // for iter


} // end of |insertion_sort()|

@ @<Include files@>=
#include <functional>
#include <iostream>

@ @c
@<Include files@>
@<Insertion Sort@>

// a simple test of the |insertion_sort| function
int main()
{
	int lst_tmp[10];
	for (int i = 0; i != 10; ++i)
		lst_tmp[i] = (3 * i) % 10;

	insertion_sort(lst_tmp, lst_tmp + 9);

	for (int i = 0; i != 10; ++i)
		std::cout << lst_tmp[i]
			<< std::endl;

	return 0;
}