Insertion Sort Algorithm

Insertion Sort works on the same principle we intuitively use to sort the cards in hand while playing any card game.

We select one item from the input and move it to its correct position in the sorted subset (generally to the left). This way, we move all the elements from the pending unsorted subset to their correct position in the sorted subset.

While working with data structures like an array, this movement to the correct position will require us to move the other elements to their right to make a slot for the elements being moved.

We start by comparing the element at index i to the elements on its left. We continue this comparison as long as we find elements that are more than the value at index i. As soon as the condition fails to match (say on index i-k or all the elements on the left are checked), we will shift the elements from index i-k to one position to the right so that the range will also occupy index i. And finally, we will complete the iteration by positioning the element at index i on index i-k.

Consider the following example: [3,5,1,9,8,7] and let’s start from i=1 (as there is no element to the left of 3)

First Pass

1. [3,5,1,9,8,7] - 5 is compared with 3; no change.
2. [1,3,5,9,8,7]
   1. 1 is smaller than 5
   2. 1 is smaller than 3
   3. As no more elements are left for comparison, we move 3 and 5 to the right and put 1 on the newly created slot.
3. [1,3,5,9,8,7] - no change as 9 is larger than all the elements to its left.
4. [1,3,5,8,9,7]
   1. 8 is smaller than 9
   2. 8 is larger than 5
   3. As the condition fails, only 1 element (9) passed the condition is moved to the right and 8 is placed in its position.
5. [1,3,5,7,8,9]
   1. 7 is smaller than 9
   2. 7 is smaller than 8
   3. 7 is more than 5; here, the condition fails, and 2 elements (8 and 9) that passed the test are shifted to their right, making a new slot for 7.

Following is a java implementation for this algorithm:

public void sort(int[] input){
   // assume the first element is always sorted
   // so that we can compare 2nd element with first
   for(int i = 1; i < input.length; i++){
       int index = i;
       int temp = input[i];
   
       // shift all the elements which are greater than i
       // to the right.
       while(index > 0 && input[index - 1] > temp){
           input[index] = input[index - 1];
           index--;
       }
   
       // put element on ith location on its correct position
       input[index] = temp;
   }
}

Although easy to implement and acceptable performance for small datasets, the overall complexity of this algorithm is still \(O(n^2)\), making it inefficient for large data sets.