Insertion sort is a classical sorting algorithm, in which each element is compared with its previous elements. for example {1,3,5,34,6}. 3 is compared with 1 ,since 3 is greater than 1 no interchange is required.again 5 is compared with its previous element 1 and 3. as 5 is greater than both 1 and 3 nothing would happen. now 34 is compared with 1,3,5 and since all the elements are less than 34 ,nothing would happen.Again 6 is compared with 1,3,5,34. as 6 is less than 34, at the place of 34, 6 will be placed.

```#include<stdio.h>

int main() {
int arr[] = { 1, 3, 5, 34, 6 };
int j = 0;
int size_of_arr = sizeof(arr) / sizeof(arr[0]);

for (j = 1; j < size_of_arr; j++) {
int key = arr[j];
int i = j - 1;
while ((i > -1) && (arr[i] > key)) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = key;
}

/* print output*/
int i = 0;
for (i; i < size_of_arr; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```

Insertion sort is an “in place” algorithm, no memory allocations are required.

Time Complexity:

O(N²)