Insertion sort explained with simple example

Insertion sort is one of simplest sorting algorithm which traverse through the list, picking one item at a time and place it in its place in the final sorted list. This sorting algorithm contains (n – 1) traversal.

Pros:
1) Simple algorithm and hence efficient for small list of data.
2) No extra memory needed.
3) Good for cases when list is almost sorted (only few misplaced items).

Cons:
1) Very slow algorithm. Not good for very large set of data.

Algorithm explained via example:

Let us take an example array “7 9 3 12 1”. Now we will run through this array with insertion sort algorithm to understand how it works.

First traversal (pick first two element):
{7, 9, 3, 12, 1} –> {7, 9, 3, 12, 1} , No substitution required as 7 < 9.

Second traversal (pick third element “3”):
{7, 9, 3, 12, 1} –> {3, 7, 9, 12, 1} , position of two items moved as 3 < 7 and 3 < 9.

Third traversal (pick fourth element “12”):
{3, 7, 9, 12, 1} –> {3, 7, 9, 12, 1} , No substitution required as 12 > 3, 7 and 9.

Fourth traversal (pick fifth element “1”):
{3, 7, 9, 12, 1} –> {1, 3, 7, 9, 12} , position of 4 elements moved as 1 is the lowest item.

Now the list is sorted.

Let’s have a look at the sample program for insertion sort.

void printArray(int a[] )
{
	for (int i = 0; i < 12; i++)
	{
		cout<< a[i] << ", ";
	}
	cout << endl;
}

void insertionSort()
{
	int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
	cout << "Insertion Sort" << endl;
	cout << "Initial array" << endl;
	printArray(a);

	int pos = 0;
	for (int i = 0; i &lt; 12; i++)
	{
		pos = i;
		for (int j = i - 1; j &gt;= 0; j--)
		{
			if (a[pos] &lt; a[j])
			{
				int temp = a[j];
				a[j] = a[pos];
				a[pos] = temp;
				pos--;
			}
			else
				break;
		}
	}
	cout << "Sorted Array" << endl;
	printArray(a);
}

int main()
{
    insertionSort();
}

Output of the above program is as follows:

Insertion Sort
Initial array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
Sorted Array
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Best case performance:
Best case performance comes when the list is already sorted. In this case, picked element is checked only with right most element of sorted list.
Hence, time complexity for best case scenario is O(n).

Worst case performance:
Worst case performance comes when the list is reverse sorted. In this case, total number of comparision needed are (1+ 2 + … + (n – 1) + n).
Hence, time complexity for worst case scenario is O(n*n).

Space complexity:
Since, no extra space is needed for this sorting algorithm. Hence, Space complexity is O(1).