**Insertion sort** is a one of the sorting technique used for sorting the elements.

**Insertion sort technique:-**

In this Insertion sort technique, Sorting of the element is performed by adding the element to the existing sorted list.

In this technique initially we are having only one element in a list after this we gradually insert a new element to list at its proper place in this way we will get our sorted list.

Example:-

- Insert 70 to array.

2. Insert 90.

3. Insert 30 in array.

4. Insert 100.

5. Insert 40.

In this way we get our sorted array as **30 40 70 90 100.**

Passes required for this sort is **N.**

The time complexity for Insertion sort is **O(n ^{2})** for worst case.

## Advantages of Insertion sort

- It is very simple sorting technique to implement.
- It has a great performance if we have a small set of data.
- The space required is small.

## Disadvantages of Insertion sort

- It is not good as other sorting technique.
- It is well for only small set of data.
- It required
**n**steps for sorting^{2}**N**element.

## Program

1234567891011121314151617181920212223242526272829303132333435 | #include <stdio.h>int main(){int n, array[1000], c, d, t;printf(“Enter number of elements\n”);scanf(“%d”, &n);printf(“Enter %d integers\n”, n);for (c = 0; c < n; c++) {scanf(“%d”, &array[c]);}for (c = 1 ; c <= n – 1; c++) {d = c;while ( d > 0 && array[d] < array[d-1]) {t = array[d];array[d] = array[d-1];array[d-1] = t;d–;}}printf(“Sorted list in ascending order:\n”);for (c = 0; c <= n – 1; c++) {printf(“%d\n”, array[c]);}return 0;} |

**Output of program:-**

**Enter number of elements:****5****Enter 5 integers****10 2 30 4 1****Sorted list in ascending order:****1****2****4****10****30**