### Online Classes

Results can only be achieved if you have the focused direction and crystal clear knowledge. To achieve this, you need a mentor. We will help you out by connecting with an expert mentor in the field.

Learn More

Article

# How does the Insertion Sort in DataStructures works?

2 min 56 sec read

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

## How does the Insertion Sort work?

Suppose we have an array in unsorted order (4,6,3,1)

1) In the first step, 6 will be compared with 4. Since 4 < 6 , no insertion takes place. 2) In the second step, 3 will be compared with 6. Since 3 < 6 , it must be on the left of 6 . Now on left of 6 , 4 is present so 3 will be compared with 4. Since 3 < 4, 3 must be on the left of 4. As there are no more elements present to the left of 4 , 3 will be inserted before 4.

Array will look loke this => 3,4,6,1. 3) In the third step, 1 will be compared with 6. Since 1 < 6 , it must be on the left of 6 . Now on left of 6 , 4 is present so 1 will be compared with 4. Since 1 < 4, 1 must be on the left of 4. Now on left of 4 , 3 is present so 1 will be compared with 3. Since 1 < 3, 1 must be on the left of 3. As there are no more elements present to the left of 3 , 1 will be inserted before 3.

Array will look loke this => 1,3,4,6. ## Insertion Program in C:-

This basic Insertion Sort in C programming explains the concept of how to sort the elements using Insertion sort in Data Structures.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void insertionSort(int N, int arr[]) {
int i,j;
int value;
for(i=1;i=0 && value<arr[j])
{
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=value;

for (j = 0; j < N; ++j)
{

printf("%d	", arr[j]);
}
printf("
");
printf("
");

}

}

int main(void) {

int N;
scanf("%d", &N);
int arr[N], i;
for(i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}

printf("Input Array is: ");

for(i = 0; i < N; i++) {
printf("%d	", arr[i]);
}

printf("

");

insertionSort(N, arr);

printf("Sortrd Array: 	");

for(i = 0; i < N; i++) {
printf("%d	", arr[i]);
}

printf("
");

return 0;
}
```

## Try to execute what you have learnt

Easy to use online data structure compiler where you can execute the programs in your favourite programming language.
(C, C++, Python)

Open Compiler

## HTML, CSS and Javascript Real time Web Editor

Execute your HTML, CSS and javascript code in real time with the web editor
(HTML, CSS, Bootstrap, Javascript)

Open Web Editor