Table of Contents

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} :

https://res.cloudinary.com/dc0mjpwf8/image/upload/v1590241245/ArticleImages/Sorting%20Algorithms/Insertionsort_u09dxf.png

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)

Scroll to Top