Insertion Sorting

Insertion sorting, as the name suggest, is about inserting the elements of an unsorted array to their correct position one by one. To make it clearer, lets say we have an unsorted array. We take another array, which is empty initially and then we will keep adding numbers one by one into this array at their correct positions.

Say the original array A is

5, 3, 7, 2, 6

Now we take first element and add to zeroth position of a new array B, so B is now containing 5

next we pick 3 from original array and add to first position of B, it becomes 3, 5

After step 3 B is, 3, 5, 7 and then 2, 3, 5, 7 and finally 2, 3, 5, 6, 7

We have taken 2 arrays just to make things clear, the sorting functionality can be achieved with 1 array only. Instead of taking an additional array, we will think of original array as 2 sub-parts, at any given time first N-x elements are sorted and remaining x are not sorted.

Again taking the original array A

5, 3, 7, 2, 6

Step 1: 5 (sorted till here), 3, 7, 2, 6
Step 2: 3, 5 (sorted till here), 7, 2, 6
Step 3: 3, 5, 7 (S), 2, 6
Step 4: 2, 3, 5, 7, (S) 6
Step 5: 2, 3, 5, 6, 7 – Final


If there are N elements in array, at Nth point, we know we have N-x sorted and x unsorted. We pick up next element (N-x+1)st, and need to insert it into proper position in for N-x+1 elements. So in worst case we need to make N-x comparisons (in best case 1 comparison). The process has to be repeated N times for N elements.

So in worst case we have comparisons like

1+2+3+.. +N= N*(N-1)/2 which is quadratic i.e. N*N.

In best case (sorted array) we have 1+1+1+.. N times comparison which is order of N (linear).

We generally take worst case complexity so we will say Insertion sort has complexity of N^2.