Insertion Sort

Today, we will dig into another easy to understand sorting algorithm - insertion sort. This algorithm is similar to previously discussed selection sort. The key difference is that insertion sort takes the current value and compares it against the already sorted part of the collection whereas selection sort takes the current value, compares it with the rest of the collection.

Rundown

• O(n) for best case (array is already sorted); O(n^2)

public static void InsertionSortIterative<T>(T[] items) where T : IComparable<T>
{
	int i, j;
	for (i = 1; i < items.Length; i++)
	{
		var curr = items[i];
		j = i - 1;
	   
		while ((j >= 0)  
			 && (items[j].CompareTo(curr) > 0))
		{
			items[j + 1] = items[j];
			j--;
		}
		//Step - 3: swap the value
		items[j + 1] = curr;
	}
}