## Insertion Sort Algorithm

Insertion sort is a sorting algorithm in which an unsorted element is placed at the correct position in each iteration, that is, to the position to which it belongs in a sorted array.

Insertion sort is efficient as it reduces its total number of steps if a partially sorted array is provided as input.

Steps

- Store the second element of the array separately in
`key.`

- Compare
`key`

with the first element. - If
`key`

is less than the first element, insert it**before the first element**else**insert it after the first element.** - Now, move to the third element and compare it with the elements to the left of it and then insert it in the correct position after comparison.
- Repeat the process until the entire array is sorted.

Visualisation of insertion sort with array = `{6, 2, 7, 3, 5, 4}`

:

Code

`void InsertionSort(int A[], int size) { for (int i = 1; i < size;i++) { int key = A[i]; int j = i - 1; while (key < A[j] && j >= 0) { A[j + 1] = A[j]; --j; } A[j + 1] = key; } }`

Each element is compared with all the other elements in the sorted array. For `N`

elements , there will be `N^2`

comparisons in the worst case. Therefore, the time complexity will be `O(N^2) in the worst case`

If the array is already sorted, then the time complexity will be ` O(n) `