Interview Preparation Insertion Sort

Algorithm for implementation of insertion sort is as follows

a. Start from index 1.

b. compare higher index element with all the elements at smaller index.

c. If element at smaller index number is greater than element at higer index than shift the element at smaller index towards right.

d. Store element of higher value in the last index where vacancy is created.

e. Repeating step b, c and d until the array is sorted.

Code Snippet

for(l = 1 ; l < Elecount ; l++)
{
	temp =  array[l];
	while(l > 0 && array[l-1] >temp)
	{
		array[l] = array[l-1];
		l = l - 1;
	}
	array[l] = temp;
}

For an array with n number of elements,

Best case complexity = O(n).

Average case complexity = Worst case complexity = O(n^2).