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.


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


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];
    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)

[gravityforms id="5" description="false" titla="false" ajax="true"]