Insertion Sort: A Marginal Improvement

The insertion sort iterates over each entry in a list and ensures that every element behind the cursor is in order. Thus, at the i-th iteration, every element 0..i is in order.

It does so by comparing the entry at position i to the one before it, and exchanging the two entries if i is smaller than i - 1. It keeps making these comparisons, working backwards over the list, and exchanging entries until reaching a spot where i is greater than or equal to i - 1 - its resting place.

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);
		}
	}
}

By repeating this process for every i up to n, the list size, all elements will be sorted by the time the end of the list is reached.

The exchange method is the same used in the previous post.

Insertion sort may perform better than selection sort in situations where most elements are already in order, because few exchanges will occur. However, where elements are far apart, insertion sort can exhibit up to quadratic complexity. For example, in the following list

7 4 3 2 1

the 7 and the 1 will each need to travel to the opposite end of the list, one exchange at a time. The shell sort, which will be covered in a future post, addresses this bottleneck by allowing entries to travel great distances at once.

As with selection sort, the insertion sort requires the constant space complexity of a few paltry index counters, making it useful in memory-bound contexts and in situations where a list is known to be mostly sorted already.