How InsertionSort works

InsertionSort is a sorting method which is easy to implement. InsertionSort works on the principle that you go through the array to be sorted and compare each element with its predecessor. You start at the 2nd element in the array.

The complexity behind InsertionSort is, in the bestcase $O(n)$ if the array is already sorted. Otherwise the averagecase and the worstcase is $O(n^2)$. The sorting method has one advantage and that is that it works in-place. Here we do not need a new array but process the input array directly.

How does InsertionSort work? Suppose we get an unsorted array $[1,5,3,9,7,8,6,4,2]$ , and we have to sort it with InsertionSort.

We start at the 2nd element, because we assume that the first element is already sorted. We check if the currently selected element is larger than the elements of the sorted array. It can also be that an element from the sorted array is larger than the currently selected element. With this information we can insert the element directly in the correct sorted position.

A small sketch shows how InsertionSort works in detail.

The implementation of the sorting procedure is very simple. I have implemented it here in Python.

#!/usr/bin/env python
import random

class InsertionSort(object):

	def __init__(self):
		None

	def sort(self, array):
		temp = j = 0;
		for walker in range(1, len(array)):
			j = walker
			while((j > 0) and (array[j - 1] > array[j])):
				temp = array[j -1];
				array[j - 1] = array[j];
				array[j] = temp;
				j -= 1;
		return array

if __name__ == '__main__':
	array = []
	for i in range(0, 100):
		array.append(random.randint(0, 100))


	ss = InsertionSort()
	print "unsorted" , array
	print "sorted", ss.sort(array)

The For loop wanders through the array starting from the 2nd element. The While loop takes the check and the insertion at the right place. Here the condition is that j which is the current position (walker) of our For loop, must be greater than 0 and the previous element from the array, must be greater than the current element. If one of the two conditions does not apply, the loop terminates and the element was inserted at the correct position.

A little fun fact about InsertionSort! InsertionSort and SelectionSort are both the same.