**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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#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**