Insertion Sort

Insertion Sort Algorithm

Insertion sort is a sorting algorithm in which an unsorted element is placed at the correct position in each iteration, that is, to the position to which it belongs in a sorted array.

Insertion sort is efficient as it reduces its total number of steps if a partially sorted array is provided as input.

Steps

• Store the second element of the array separately in key.
• Compare key with the first element.
• If key is less than the first element, insert it before the first element else insert it after the first element.
• Now, move to the third element and compare it with the elements to the left of it and then insert it in the correct position after comparison.
• Repeat the process until the entire array is sorted.

Visualisation of insertion sort with array = {6, 2, 7, 3, 5, 4} :

Code

void InsertionSort(int A[], int size)
 {
  for (int i = 1; i < size;i++)
  {
    int key = A[i];
    int j = i - 1;
    while (key < A[j] && j >= 0)
     {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

Each element is compared with all the other elements in the sorted array. For N elements , there will be N^2 comparisons in the worst case. Therefore, the time complexity will be O(N^2) in the worst case

If the array is already sorted, then the time complexity will be O(n)