Insertion Sort

Insertion Sort is an in place comparison based sorting algorithm, which is commonly used in Computer Science. This algorithm is just similar to the way we sort a deck of cards while playing bridge. The main idea behind insertion list is that it inserts each item into its proper place in the final sorted array.

How does Insertion Sort Work ?

• The array of values to be sorted is divided into two parts. One stores the sorted values while the other consists of the unsorted values.
• This algorithm continues until the unsorted part is empty.
• Assume there are n elements in the array. Initially the first element is in the sorted part while the rest in the unsorted part.
• During each iteration, the first element in the unsorted part is picked and inserted into the correct position in the sorted array.

The way in which a given array is arranged using Selection Sort Algorithm is depicted in the following diagram.

Pseudo Code for Selection Sort

INSERTION-SORT(A)
   for i = 1 to n
    key ← A [i]
        j ← i – 1
     while j > = 0 and A[j] > key
        A[j+1] ← A[j]
        j ← j – 1
    End while 
    A[j+1] ← key
  End for 

Implementation of Selection Sort in C

void Insertion_Sort ( int A[ ] , int n) 
{
     for( int i = 0 ;i < n ; i++ ) {
    //storing current element whose left side is checked for its correct position //

      int key = A[ i ];    
      int j = i;

       /* check whether the adjacent element in left side is greater or
            less than the current element. */

          while(  j > 0  && key < A[ j -1]) {

           // moving the left side element to one position forward.
                A[ j ] = A[ j-1];   
                j= j - 1;

           }
         // moving current element to its  correct position.
           A[ j ] = key;       
     }  
}

Complexity of Insertion Sort

Time Complexities

• Best Case Complexity : O (n)
  This occurs when the array is already sorted. The outer loops runs n number of times while the inner loop does not run at all. Therefore, there are only n number of comparisons such that complexity is linear.

• Worst Case Complexity : O (n^2)
  The worst case occurs when the elements in the array are in the reversed order. Here, the first element of the unsorted part has to be compared with every elements in the sorted part. Therefore it has a quadratic running time.

• Average Case Complexity : O(n^2)
  It occurs when the elements in the array is in neither ascending nor descending order.

Space Complexity
Space Complexity is O(1) as an extra variable key is used.

Advantages of Insertion Sort

• It requires less memory space (only O(1) of additional memory space)
• It is easy to implement.
• It is efficient to use on small sets of data.

By reading the above blog post, I hope you would have gained a sound knowledge on Insertion Sort.