Insertion Sort

insertion-sort.h

#include <vector>

template<typename T>
void exchange(vector<T>& list, int i, int j)
{
	T temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

/**
 * In an insertion sort, which represents a marginal
 * improvement over selection sort, we iterate
 * from start to end as usual. However, at every encountered
 * item, we work backwards over the list, comparing it to
 * each earlier item and swapping as necessary, until that item
 * is at its proper location. In this way, at every 'i',
 * all previous elements are in sorted order. By the time
 * the end is reached, all elements are in order.
 * Where each element is already in its appropriate place,
 * there will no movement at all. However, in the worst case,
 * the sort exhibits quadratic complexity (O(n2)), because
 * it also has two inner loops.
 */
template<typename T>
void insertion_sort(vector<T>& list)
{
	for (int i = 0; i < list.size(); ++i)
	{
		for (int j = i; j > 0 && list[j] < list[j - 1]; --j)
		{
			exchange(list, j, j - 1);
		}
	}
}