Group Discounts available for 3+ students and Corporate Clients

Insertion sort in Data Structures

Insertion sort

Suppose an array ‘A’ with ‘n’ elements A[0]. A910,A[20],———A[N-1] is in memory. The insertion sort algorithm in data structures scans ‘A; from A[0] to A[N-1] insert each element A[k] into its proper position in the previously sorted sub array A[0],A[1],A[2]—-

A[K]                      That is

pass1                   A[0] by itself ip trivially sorted.

pass2                   A[1] is inserted either before or after aA[0]

So that : A[0],A[1] is sorted

pass3: A[2] is inserted into its proper place in

A[1] A[2], that is before A[0] between A[0]

A[1] or after A[1], so that : A[0],A[1],A[2] is sorted

pass4: [3] is inserted into its proper place in A[1],A[2] so that : A[0],A[1],A[2],A[3] is sorted.

PassN : A[N] is inserted into its proper place in A[1],A[2],——-A[N-1] so that : A[0],A[1]— is sorted.


Example :




Insertion Sort Program

Implementation of insertion sort in data structures

# include <stdio.h>

# include <conio.h>

void main()


int n,i,j,a[20],temp;

void insertion sort(int  a[10],int n);


printf(“Enter n value: ”);


printf(“Enter the elements:\n”);

for(i=0; i<n;i++)




Insertion sort(a,n);


insertion sort(a,n);

printf(“The sorted elements are:\n”);






void insertion sort (int a[20], int n)


int i,j,temp;












output :

Enter ‘n’ value : 5

Enter the elements:     2       4       3       1       5

The elements are :  2   3       4       5



Time complexity :      

Algorithm Worst case Average case
Insertion sort n(n+1)/2=o(n2) n(n-1)/4=o(n2)



“At TekSlate, we are trying to create high quality tutorials and articles, if you think any information is incorrect or want to add anything to the article, please feel free to get in touch with us at, we will update the article in 24 hours.”

0 Responses on Insertion sort in Data Structures"

Leave a Message

Your email address will not be published. Required fields are marked *


Please Enter Your Details and Query.
Three + 6